Визуализация
Искомое: В случайном месте
Легенда цветов
Как работает двоичный поиск
Идея алгоритма. Чтобы быстро найти слово в словаре, мы открываем его ровно посередине. Если нужное слово по алфавиту идет раньше - отбрасываем правую половину словаря. Если позже - отбрасываем левую. Затем снова открываем оставшуюся часть посередине. И так до тех пор, пока не найдем искомое.
Границы поиска. Алгоритм использует два указателя: lo (левая граница) и hi (правая граница). Изначально они охватывают весь массив [0, n-1]. На каждом шаге мы проверяем элемент mid = (lo + hi) / 2.
Условие завершения. Поиск успешно завершается, когда a[mid] совпал с искомым значением. Если же левая граница перешагнула правую (lo > hi), значит, мы сузили диапазон до нуля, а элемента так и не встретили - в этом случае поиск возвращает неудачу (например, -1).
Синонимы названия. Этот алгоритм также известен как бинарный поиск, метод половинного деления и дихотомия.
Сложность алгоритма
Сложность - это оценка того, как быстро растет потребление ресурса при росте длины массива n. Оценки записывают через O-нотацию - у нас есть отдельная анимация о том, как читать такие записи.
По времени
Показывает, как растет число операций (здесь это сравнения элементов) при росте n. Двоичный поиск работает за логарифмическое время O(log n). С каждым шагом количество оставшихся элементов уменьшается ровно в два раза.
| Случай | Время | Комментарий |
|---|---|---|
| Лучший (элемент ровно в середине) | O(1) | Нашли на первом же делении массива пополам |
| Средний | O(log n) | Диапазон стабильно сужается вдвое на каждом шаге |
| Худший (элемента нет или он на краю) | O(log n) | Делим пополам, пока диапазон [lo, hi] не схлопнется |
По памяти
Показывает, сколько дополнительной памяти нужно алгоритму помимо самого массива.
| Характеристика | Оценка | Комментарий |
|---|---|---|
| Дополнительная память | O(1) | Хватает двух переменных для хранения границ lo и hi |
Требования к данным
| Характеристика | Оценка | Комментарий |
|---|---|---|
| Требует сортировки? | Да | Алгоритм обязан получать на вход отсортированный массив. Если данные не отсортированы, то "отбросить половину" нельзя, и придется использовать линейный поиск. |
Примеры реализации двоичного поиска (Binary Search)
Код на C
// Возвращает индекс найденного элемента или -1, если элемента нет
int binary_search(int arr[], int n, int target) {
int lo = 0;
int hi = n - 1;
// Пока диапазон не пуст
while (lo <= hi) {
// Защита от переполнения: lo + (hi - lo) / 2
int mid = lo + (hi - lo) / 2;
if (arr[mid] == target) {
return mid; // Элемент найден
}
if (arr[mid] < target) {
// Искомое правее, отбрасываем левую половину
lo = mid + 1;
} else {
// Искомое левее, отбрасываем правую половину
hi = mid - 1;
}
}
return -1; // Элемент не найден
}Код на Python
# Возвращает индекс найденного элемента или -1, если элемента нет
def binary_search(arr, target):
lo = 0
hi = len(arr) - 1
# Пока диапазон не пуст
while lo <= hi:
# В Python целые числа не переполняются
mid = (lo + hi) // 2
if arr[mid] == target:
return mid # Элемент найден
if arr[mid] < target:
# Искомое правее, сдвигаем левую границу
lo = mid + 1
else:
# Искомое левее, сдвигаем правую границу
hi = mid - 1
return -1 # Элемент не найденКод на JavaScript
// Возвращает индекс найденного элемента или -1, если элемента нет
function binarySearch(arr, target) {
let lo = 0;
let hi = arr.length - 1;
// Пока диапазон не пуст
while (lo <= hi) {
// Битовый сдвиг вправо на 0 заменяет Math.floor()
let mid = (lo + hi) >>> 1;
if (arr[mid] === target) {
return mid; // Элемент найден
}
if (arr[mid] < target) {
// Искомое правее, отбрасываем левую половину
lo = mid + 1;
} else {
// Искомое левее, отбрасываем правую половину
hi = mid - 1;
}
}
return -1; // Элемент не найден
}