Binary Search in PHP: A Complete Guide with Iterative and Recursive Examples

Binary search is an algorithm for locating a target value within a sorted array. Instead of scanning every element (linear search, O(n)), it repeatedly halves the search range, giving a time complexity of O(log n).

How it works

The array must be sorted. You track a search window with two pointers, low and high:

1. Compute the middle index mid = (low + high) / 2.

2. Compare the middle element to the target.

   • Equal → found it, return the index.
   • Middle is less than target → discard the left half, set low = mid + 1.
   • Middle is greater than target → discard the right half, set high = mid - 1.

3. Repeat until the value is found or low > high (not present).

Each step eliminates half the remaining elements, so a 1,000,000-element array takes at most ~20 comparisons.

Complexity

Case	Time	Space (iterative)
Best	O(1)	O(1)
Avg	O(log n)	O(1)
Worst	O(log n)	O(1)

The recursive variant uses O(log n) space for the call stack.

Iterative implementation (PHP)

/**
 * Iterative binary search.
 *
 * @param array $arr    Sorted array of comparable values.
 * @param mixed $target Value to find.
 * @return int          Index of target, or -1 if not found.
 */
function binarySearch(array $arr, $target): int
{
    $low = 0;
    $high = count($arr) - 1;

    while ($low <= $high) {
        // Avoids integer overflow on very large bounds.
        $mid = $low + intdiv($high - $low, 2);

        if ($arr[$mid] === $target) {
            return $mid;
        }

        if ($arr[$mid] < $target) {
            $low = $mid + 1;
        } else {
            $high = $mid - 1;
        }
    }

    return -1;
}

// Example
$numbers = [1, 3, 5, 7, 9, 11, 13, 15];

echo binarySearch($numbers, 9); // 4
echo "\n";
echo binarySearch($numbers, 6); // -1

Recursive implementation (PHP)

function binarySearchRecursive(array $arr, $target, int $low, int $high): int
{
    if ($low > $high) {
        return -1;
    }

    $mid = $low + intdiv($high - $low, 2);

    if ($arr[$mid] === $target) {
        return $mid;
    }

    if ($arr[$mid] < $target) {
        return binarySearchRecursive($arr, $target, $mid + 1, $high);
    }

    return binarySearchRecursive($arr, $target, $low, $mid - 1);
}

// Example
$numbers = [2, 4, 6, 8, 10, 12];

echo binarySearchRecursive(
    $numbers,
    8,
    0,
    count($numbers) - 1
); // 3

Common pitfalls

• Unsorted input. Binary search only works on sorted data. Sort first (sort($arr)), but note that sorting is O(n log n)—if you search once, linear search may be cheaper.
• Overflow. Use $low + intdiv($high - $low, 2) rather than intdiv($low + $high, 2). PHP auto-promotes to float on overflow, but the safer form keeps the index an integer.
• Strict vs loose comparison. === avoids type juggling, for example 0 == "abc" was true before PHP 8. Use it when your array holds mixed or string-y data.
• Off-by-one in bounds. high starts at count($arr) - 1, and the loop condition is low <= high, not <.

When to use it

Binary search shines on large, sorted, randomly-accessible collections that are searched repeatedly. For small arrays or data you search only once, the cost of sorting often outweighs the benefit, and a simple linear scan is fine. PHP's built-in in_array / array_search are linear; there's no native binary search, so the implementations above fill that gap.