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

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

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

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

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

Пример кода на 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; // элемент не найден
}

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

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

Вывод

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