Что такое бинарный поиск?

Что такое бинарный поиск?

Бинарный поиск — это эффективный алгоритм для поиска элемента в отсортированном массиве. В отличие от линейного поиска, который проверяет каждый элемент по порядку, бинарный поиск использует стратегию "разделяй и властвуй", что позволяет значительно сократить количество операций.

Как он работает?

Алгоритм начинает с определения границ массива (левый и правый индексы). Затем он находит средний элемент и сравнивает его с искомым значением. Если средний элемент равен искомому, поиск завершён. Если искомое значение меньше среднего, поиск продолжается в левой половине массива, иначе — в правой. Этот процесс повторяется, пока границы не сойдутся или элемент не будет найден.

Пример на JavaScript

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

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid; // элемент найден
    } else if (arr[mid] < target) {
      left = mid + 1; // ищем в правой половине
    } else {
      right = mid - 1; // ищем в левой половине
    }
  }

  return -1; // элемент не найден
}

Где применяется?

Бинарный поиск используется в различных областях: поиск в отсортированных базах данных, реализация функций поиска в стандартных библиотеках (например, Array.prototype.indexOf в JavaScript может использовать бинарный поиск для отсортированных массивов), а также в алгоритмах, требующих быстрого поиска, таких как поиск корня уравнения или определение точки вставки.

Вывод

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