(реализация JavaScript)

Этот алгоритм поиска работает по принципу «разделяй и властвуй». Для правильной работы этого алгоритма есть большой нюанс: сбор данных должен быть отсортирован.

Временная сложность:

  • Наихудший и средний случай: O(log n)
  • Лучший вариант: O(1)

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

Бинарный поиск сравнивает искомый элемент со средним элементом коллекции. Если есть совпадение, он вернет индекс среднего элемента. Если средний элемент короче искомого элемента, мы забываем о подмассиве от середины вправо и повторяем операцию поиска подмассива слева до среднего элемента.
Мы продолжаем этот процесс, пока не найдем элемент или пока размер подмассива не достигнет 0.

Давайте попробуем разобраться, рассматривая алгоритм шаг за шагом:

Псевдокод:

// Write a function that accepts a sorted array and a value.
// Create a left pointer at the start of the array and a right
   pointer at the end.  
// While the left pointer comes before the right pointer:
// Create a pointer in the middle
// If you find the value you want, return the index.
// If the value is too small, move the left pointer up.
// If the value is too large, move the right pointer down.
// Return -1 if the value is never found.

Код: