Бінарний пошук

Ідея

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 індекси у БД, пошук вставки, алгоритми типу «бінарний пошук за відповіддю».