Binary Search Algorithm in PHP

Binary Search algorithm has runtime complexity of O(log n) for worst case and average case, and O(1) for the best case.

There is recursive and iterative implementation of Binary Search. I will write iterative implementation here. I prefer it over recursive because it is easy to understand. The space complexity of iterative implementation is O(1).

function binarySearch(array $sortedArray, $needle) : int
{
    $low = 0;
    $high = count($sortedArray) - 1;

    while ($low <= $high) {
        $middle = ($low + $high) / 2;

        if ($sortedArray[$middle] < $needle) {
            $low = $middle + 1;
        } else if ($sortedArray[$middle] > $needle) {
            $high = $middle - 1;
        } else {
            return $middle;
        }
    }

    return -1; // Unable to find needle
}

Source Code of Algorithm Series: https://github.com/EresDev/Algorithms

Leave a Reply

avatar
  Subscribe  
Notify of