PHP Program for Binary Search with Example and Explanation

A PHP program for binary search uses a while loop to repeatedly divide the sorted array and compare the middle element with the target, like this: function binarySearch(array $arr, int $target): int { $low = 0; $high = count($arr) - 1; while ($low <= $high) { $mid = intdiv($low + $high, 2); if ($arr[$mid] === $target) return $mid; elseif ($arr[$mid] < $target) $low = $mid + 1; else $high = $mid - 1; } return -1; }.

Examples

Input[1, 3, 5, 7, 9], target=7

Output3

Input[2, 4, 6, 8, 10], target=5

Output-1

Input[10], target=10

Output0

How to Think About It

To perform binary search, start with the whole sorted list. Check the middle item. If it matches the target, return its position. If the target is smaller, repeat the search on the left half. If larger, repeat on the right half. Keep doing this until you find the target or the search space is empty.

Algorithm

1

Set low to 0 and high to the last index of the array.

2

While low is less than or equal to high:

3

Calculate mid as the middle index between low and high.

4

If the element at mid equals the target, return mid.

5

If the element at mid is less than the target, set low to mid + 1.

6

Otherwise, set high to mid - 1.

7

If the loop ends without finding the target, return -1.

Code

php

<?php
function binarySearch(array $arr, int $target): int {
    $low = 0;
    $high = count($arr) - 1;
    while ($low <= $high) {
        $mid = intdiv($low + $high, 2);
        if ($arr[$mid] === $target) {
            return $mid;
        } elseif ($arr[$mid] < $target) {
            $low = $mid + 1;
        } else {
            $high = $mid - 1;
        }
    }
    return -1;
}

// Example usage:
$array = [1, 3, 5, 7, 9];
$target = 7;
$result = binarySearch($array, $target);
echo $result;

Output

3

Dry Run

Let's trace searching for 7 in [1, 3, 5, 7, 9] through the code

1

Initialize pointers

low = 0, high = 4 (array length - 1)

2

First iteration

mid = intdiv(0 + 4, 2) = 2; arr[mid] = 5; 5 < 7, so low = mid + 1 = 3

3

Second iteration

low = 3, high = 4; mid = intdiv(3 + 4, 2) = 3; arr[mid] = 7; found target, return 3

low	high	mid	arr[mid]	action
0	4	2	5	5 < 7, set low = 3
3	4	3	7	7 == 7, return 3

Why This Works

Step 1: Divide and conquer

The code splits the array into halves by calculating the middle index with intdiv, focusing only on the half where the target could be.

Step 2: Adjust search range

If the middle element is less than the target, the search continues in the right half by moving low up; if greater, it moves high down to search the left half.

Step 3: Return result

If the target is found, the function returns its index; if not found after the search space is empty, it returns -1.

Alternative Approaches

Recursive binary search

php

<?php
function binarySearchRecursive(array $arr, int $target, int $low, int $high): int {
    if ($low > $high) return -1;
    $mid = intdiv($low + $high, 2);
    if ($arr[$mid] === $target) return $mid;
    elseif ($arr[$mid] < $target) return binarySearchRecursive($arr, $target, $mid + 1, $high);
    else return binarySearchRecursive($arr, $target, $low, $mid - 1);
}

// Usage:
$array = [1, 3, 5, 7, 9];
$target = 7;
echo binarySearchRecursive($array, $target, 0, count($array) - 1);

Uses recursion instead of a loop; easier to read but uses more memory due to call stack.

Using PHP built-in function array_search

php

<?php
$array = [1, 3, 5, 7, 9];
$target = 7;
$index = array_search($target, $array);
echo $index !== false ? $index : -1;

Simplest approach but does a linear search, not binary, so slower on large arrays.

Complexity: O(log n) time, O(1) space

Time Complexity

Binary search halves the search space each step, so it runs in logarithmic time, O(log n), where n is the number of elements.

Space Complexity

The iterative version uses constant extra space O(1), only storing a few variables for indexes.

Which Approach is Fastest?

Iterative binary search is fastest and most memory efficient; recursive uses more stack space; linear search is slower for large arrays.

Approach	Time	Space	Best For
Iterative Binary Search	O(log n)	O(1)	Large sorted arrays with memory constraints
Recursive Binary Search	O(log n)	O(log n)	Readable code, smaller arrays
Linear Search (array_search)	O(n)	O(1)	Unsorted or small arrays