Glossary

Binary Search

Binary search is a search algorithm for a sorted array with O(log n) complexity. Instead of checking every element, the search space is halved at each step. One billion elements — at most 30 iterations.

Idea

Compare the target value with the middle element
If equal — found
If target is smaller — search the left half
If larger — search the right half
Repeat

Example

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

Where it is used

Searching sorted data, B-Tree indexes in databases, finding insertion points, "binary search on the answer" algorithm techniques.