Как уменьшается диапазон поиска при бинарном поиске?

Как уменьшается диапазон поиска при бинарном поиске

Бинарный поиск — это эффективный алгоритм для поиска элемента в отсортированном массиве. Его ключевая идея заключается в том, чтобы на каждом шаге делить текущий диапазон поиска пополам, отбрасывая ту половину, в которой заведомо нет искомого элемента. Это позволяет достичь логарифмической сложности O(log n).

Принцип работы

Алгоритм начинает с полного диапазона от левого индекса (low) до правого (high). Вычисляется средний индекс (mid). Если значение в mid равно искомому, поиск завершён. Если искомое значение меньше значения в mid, то все элементы справа от mid больше искомого, поэтому диапазон сужается до [low, mid-1]. Если больше — диапазон становится [mid+1, high].

Пример на JavaScript

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

Визуализация уменьшения диапазона

Рассмотрим массив [1, 3, 5, 7, 9, 11, 13] и поиск числа 7:

• Шаг 1: low=0, high=6, mid=3 (значение 7) — найдено.
• Если бы искали 5: low=0, high=6, mid=3 (7 > 5) → high=2; затем low=0, high=2, mid=1 (3 < 5) → low=2; low=2, high=2, mid=2 (5) — найдено.

Каждый шаг сокращает количество рассматриваемых элементов вдвое. Для массива из 8 элементов потребуется не более 4 шагов, для 16 — не более 5, и так далее.

Вывод

Бинарный поиск применяется везде, где данные отсортированы и требуется быстрый поиск: в базах данных, поисковых системах, при работе с большими наборами данных. Его эффективность делает его незаменимым инструментом в арсенале разработчика.