Бинарный поиск

Идея

1. Сравнить целевое значение со средним элементом
2. Если равны — найдено
3. Если цель меньше — искать в левой половине
4. Если больше — в правой
5. Повторять

Пример

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;
}

Где используется

Поиск в отсортированных данных, B-Tree индексы в БД, нахождение точки вставки, алгоритмы типа «бинарный поиск по ответу».