Binary Search with PHP

Welcome to today's lesson! We're diving into Binary Search, a clever technique for locating specific elements within a sorted list. By repeatedly dividing the search interval in half, we can find the targeted item. It's akin to flipping through a dictionary — instead of going page by page, you'd start in the middle and then narrow down the section in half until you find your desired word.

Binary Search begins at the midpoint of a sorted list, halving the search area at each step until it locates the target. For example, if we were to look for the number 9 in a sorted list ranging from 1 to 10, we would start at the midpoint, 5. Since 9 is larger than the midpoint, we discard all numbers less than or equal to 5 and focus on the second half, leaving us with numbers 6 to 10. Next, we find the midpoint of this subset, which is 8. Since 9 is greater than 8, we eliminate numbers 6 through 8, leaving us with just 9 and 10. Now, the midpoint of this final subset is 9, which matches our target. Thus, we've located the number 9 after three steps, demonstrating how Binary Search efficiently narrows the search range with each comparison.

Let's see how Binary Search can be implemented in PHP, taking a recursive approach. This process involves a function calling itself — with a base case in place to prevent infinite loops — and a recursive case to solve smaller parts of the problem.

function binarySearch(array $arr, int $start, int $end, int $target): int {
    if ($start > $end) return -1; // Base case
    $mid = $start + (int)(($end - $start) / 2); // Find the midpoint
    if ($arr[$mid] == $target) return $mid; // Target found
    if ($arr[$mid] > $target) // If the target is less than the midpoint
        return binarySearch($arr, $start, $mid - 1, $target); // Search the left half
    return binarySearch($arr, $mid + 1, $end, $target); // Else, search the right half
}

Within this code, the base case is defined first. If the start index is greater than the end index, it indicates the search area is exhausted, resulting in a -1 return. The code then locates the midpoint. If the midpoint equals our target, it’s returned. Depending on whether the target is less or more than the midpoint, the search continues within the left or right half, respectively.