PHP Program for Binary Search Using Recursion

A PHP program for binary search using recursion defines a function like function binarySearch(array $arr, int $low, int $high, int $target): int that checks the middle element and recursively searches the left or right half until the target is found or the range is empty.

Examples

Input[1, 2, 3, 4, 5], target=3

Output2

Input[10, 20, 30, 40, 50], target=25

Output-1

Input[5], target=5

Output0

How to Think About It

To perform a binary search recursively, start by checking the middle element of the sorted array. If it matches the target, return its index. If the target is smaller, repeat the search on the left half; if larger, on the right half. Continue this until the target is found or the search range is empty.

Algorithm

1

Start with the full array range defined by low and high indexes.

2

Find the middle index between low and high.

3

Compare the middle element with the target value.

4

If equal, return the middle index.

5

If target is less, recursively search the left half.

6

If target is greater, recursively search the right half.

7

If low exceeds high, return -1 indicating not found.

Code

php

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

// Example usage
$array = [1, 2, 3, 4, 5];
$target = 3;
$result = binarySearch($array, 0, count($array) - 1, $target);
echo $result;

Output

2

Dry Run

Let's trace the search for target 3 in array [1, 2, 3, 4, 5] through the code.

1

Initial call

low=0, high=4, mid=2, arr[mid]=3, target=3

2

Check middle element

arr[mid] equals target, return mid=2

Call	low	high	mid	arr[mid]	target	Action
1	0	4	2	3	3	Found target, return 2

Why This Works

Step 1: Divide the array

The function calculates the middle index to split the array into halves using intdiv.

Step 2: Compare middle element

It compares the middle element with the target to decide which half to search next.

Step 3: Recursive search

The function calls itself on the left or right half depending on the comparison until it finds the target or the range is empty.

Alternative Approaches

Iterative binary search

php

<?php
function binarySearchIterative(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) {
            $high = $mid - 1;
        } else {
            $low = $mid + 1;
        }
    }
    return -1;
}

// Example usage
$array = [1, 2, 3, 4, 5];
$target = 3;
echo binarySearchIterative($array, $target);

Uses a loop instead of recursion, which can be more memory efficient for large arrays.

Using built-in PHP functions

php

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

Simpler but not a binary search; uses linear search internally, so slower for large sorted arrays.

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

Time Complexity

Binary search divides the search range in half each step, so it runs in logarithmic time relative to the array size.

Space Complexity

Recursive calls add to the call stack, so space complexity is O(log n) due to recursion depth.

Which Approach is Fastest?

Iterative binary search uses O(1) space and is generally faster in practice due to no recursion overhead.

Approach	Time	Space	Best For
Recursive binary search	O(log n)	O(log n)	Clear recursive logic, smaller arrays
Iterative binary search	O(log n)	O(1)	Large arrays, memory efficient
Linear search (array_search)	O(n)	O(1)	Unsorted arrays or small data