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