Binary Search: Explanation and PHP Implementations

Binary search is a fast searching algorithm that repeatedly halves a sorted array to find the position of a target value, achieving a time complexity of O(log n). It works by comparing the middle element with the target and narrowing the search range accordingly.

The algorithm follows these steps: start with the whole sorted array, set left and right pointers to the first and last indices, compute the middle index, compare the middle element with the target, return the index if equal, otherwise move the left pointer to mid+1 if the target is larger or move the right pointer to mid-1 if the target is smaller, and repeat until the target is found or the range becomes empty.

This method is particularly effective for large sorted datasets because it reduces the search space exponentially with each iteration.

Below is an iterative PHP implementation of binary search:

<?php
function binarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;
    while ($left <= $right) {
        $mid = floor(($left + $right) / 2);
        // Check if the target value is found at the middle index
        if ($arr[$mid] === $target) {
            return $mid;
        }
        // If the target is greater, ignore the left half
        if ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else { // If the target is smaller, ignore the right half
            $right = $mid - 1;
        }
    }
    // Target value not found in the array
    return -1;
}
// Example usage 1
$sortedArray = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
$targetValue = 91;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
    echo "Target value not found in the array.<br>";
} else {
    echo "Target value found at index $resultIndex.<br>";
}
// Example usage 2
$targetValue = 42;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
    echo "Target value not found in the array.";
} else {
    echo "Target value found at index $resultIndex.";
}
?>

The first example prints "Target value found at index 9." for the target 91, while the second example reports that the target 42 is not present.

A recursive version of binary search in PHP is shown below:

<?php
function binarySearchRecursive($arr, $target, $left, $right) {
    if ($left > $right) {
        // Target value not found in the array
        return -1;
    }
    $mid = floor(($left + $right) / 2);
    // Check if the target value is found at the middle index
    if ($arr[$mid] === $target) {
        return $mid;
    }
    // If the target is greater, search the right half
    if ($arr[$mid] < $target) {
        return binarySearchRecursive($arr, $target, $mid + 1, $right);
    }
    // If the target is smaller, search the left half
    return binarySearchRecursive($arr, $target, $left, $mid - 1);
}
// Wrapper function for the recursive binary search
function binarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;
    return binarySearchRecursive($arr, $target, $left, $right);
}
// Example usage
$sortedArray = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
$targetValue = 16;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
    echo "Target value not found in the array.";
} else {
    echo "Target value found at index $resultIndex.";
}
?>

This recursive example outputs "Target value found at index 4." for the target 16, demonstrating the same logical flow as the iterative version but using function calls instead of a loop.

In conclusion, binary search is a powerful algorithm for efficiently locating values in sorted arrays, with both iterative and recursive PHP implementations offering reliable performance; the iterative approach is straightforward and low‑overhead, while the recursive version provides a cleaner, though slightly more stack‑intensive, solution.