Бинарный поиск | Алгоритмы

Представьте, перед вами большой толстый бумажный словарь, в котором необходимо найти раздел с буквой X. Вы не листаете его страницу за страницей, начиная с буквы A (пока не дойдете до X). Нет! Вы открываете книгу примерно посередине, смотрите, какая там буква, и отбрасываете половину словаря. Потом ещё раз делите пополам, и ещё - это и есть бинарный поиск.

Бинарный поиск (binary search) — это алгоритм для нахождения позиции конкретного элемента в отсортированном списке.

В основе лежит принцип «разделяй и властвуй». Алгоритм сравнивает искомое значение с элементом в середине текущего диапазона. Если значение совпадает — элемент найден. Если искомое значение меньше центрального — поиск продолжается в левой половине, если больше — в правой. На каждом шаге область поиска сужается вдвое.

О-большое

Обычный линейный поиск проходит элементы один за другим. В худшем случае, если элемента нет в коллекции, придется проверить каждый из N элементов. Его вычислительная сложность — O(n). Если в списке 1млн элементов, потребуется проверить все 1млн элементов в худшем случае.

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

На практике это означает следующее: если у вас есть отсортированный массив на 1млн элементов, то бинарному поиску для этого потребуется не более 20 итераций (log₂ 1,000,000 ≈ 20). Разница колоссальна!

И под конец рассмотрим простой пример с использованием бинарного поиска, где нам нужно найти заданный target в отсортированном списке. Написал следующую функцию:

func search(nums []int, target int) int {

  // еще пишут: start/end
  left, right := 0, len(nums)-1

  for left <= right {

    // формула нахождения середины
    mid := left + (right-left)/2

    switch {

    // если нашли target - возвращаем
    case nums[mid] == target:
      return mid

    // если искомый элемент справа
    // обрезаем левую часть
    case nums[mid] < target:
      left = mid + 1

    // если искомый элемент слева
    // обрезаем правую часть
    case nums[mid] > target:
      right = mid - 1

    }
  }

  return -1
}

p.s. более наглядно работу бинарного поиска видно на Gif'ках.