Бинарный поиск
Последнее обновление
Бинарный поиск находит целевое значение в **отсортированном** массиве, многократно деля окно поиска пополам. Он сравнивает средний элемент с целью: совпадение завершает поиск; иначе половина, которая не может содержать цель, отбрасывается, и окно сужается до другой половины. Каждое сравнение исключает половину оставшихся элементов — поэтому алгоритм работает за O(log n): поиск среди миллиона отсортированных значений требует не более примерно 20 сравнений.
Анимация выше показывает указатели lo, mid и hi и затемняет исключённую половину после каждого сравнения. Единственное непреложное условие: массив уже должен быть отсортирован — для неотсортированных данных нужен линейный поиск или сначала сортировка (см. сортировку слиянием). Та же идея деления пополам лежит в основе двоичного дерева поиска.
Временная и пространственная сложность
| Случай | Сложность | Примечания |
|---|---|---|
| Лучший случай | O(1) | Средний элемент оказывается целью при первом же сравнении. |
| Средний случай | O(log n) | Каждое сравнение делит оставшееся окно пополам. |
| Худший случай | O(log n) | Окно сужается до одного элемента, прежде чем найти цель или убедиться в её отсутствии. |
| Память | O(1) | Итеративная версия хранит только индексы lo, hi и mid. |
Шаг за шагом
| Шаг | Что происходит |
|---|---|
| 1 | Установите lo на первый индекс, а hi — на последний индекс отсортированного массива. |
| 2 | Вычислите средний индекс: mid = (lo + hi) // 2. |
| 3 | Если a[mid] равен цели, верните mid — найдено. |
| 4 | Если a[mid] **меньше** цели, цель может быть только в правой половине: установите lo = mid + 1. |
| 5 | Если a[mid] **больше** цели, ищите в левой половине: установите hi = mid - 1. |
| 6 | Повторяйте с шага 2, пока lo <= hi; если окно опустело, цели в массиве нет. |
Разобранный пример
Поиск 5 в [1, 2, 3, 5, 7, 8, 9]:
| Проход | Окно (lo..hi) | mid | a[mid] | Действие |
|---|---|---|---|---|
| 1 | [1, 2, 3, 5, 7, 8, 9] (0..6) | 3 | 5 | a[3] = 5 — цель найдена по индексу 3. |
Промах, шаг за шагом
Поиск 4 в том же массиве показывает, как окно пустеет:
| Проход | Окно (lo..hi) | mid | a[mid] | Действие |
|---|---|---|---|---|
| 1 | 0..6 | 3 | 5 | 5 > 4 — ищем в левой половине, hi = 2. |
| 2 | 0..2 | 1 | 2 | 2 < 4 — ищем в правой половине, lo = 2. |
| 3 | 2..2 | 2 | 3 | 3 < 4 — lo становится 3, окно пустеет: не найдено. |
Когда использовать бинарный поиск
| Используйте, когда | Избегайте, когда |
|---|---|
| Данные уже отсортированы (или вы ищете в них много раз) | Данные не отсортированы и ищутся лишь один раз — предварительная сортировка стоит O(n log n) |
| Коллекция поддерживает быстрый произвольный доступ (массивы) | У вас есть только последовательный доступ (связные списки) |
Набор данных большой — O(log n) особенно хорош в масштабе | Набор данных крошечный — простой перебор так же быстр и проще |
Код Binary Search
Чистая, готовая к запуску реализация Binary Search на Python, JavaScript, Java, C++, C, Pseudocode. Выберите язык, скопируйте код или откройте его уже загруженным в плейграунде Coddy.
Код Binary Search на Python
Python
1def binary_search(a, target):2 lo, hi = 0, len(a) - 13 while lo <= hi:4 mid = (lo + hi) // 25 if a[mid] == target:6 return mid7 if a[mid] < target:8 lo = mid + 1 # search the right half9 else:10 hi = mid - 1 # search the left half11 return -112
13
14nums = [1, 2, 3, 5, 7, 8, 9] # must be sorted15print("Index of 5:", binary_search(nums, 5))16print("Index of 4:", binary_search(nums, 4))Код Binary Search на JavaScript
JavaScript
1function binarySearch(a, target) {2 let lo = 0;3 let hi = a.length - 1;4 while (lo <= hi) {5 const mid = Math.floor((lo + hi) / 2);6 if (a[mid] === target) return mid;7 if (a[mid] < target) {8 lo = mid + 1; // search the right half9 } else {10 hi = mid - 1; // search the left half11 }12 }13 return -1;14}15
16const nums = [1, 2, 3, 5, 7, 8, 9]; // must be sorted17console.log("Index of 5:", binarySearch(nums, 5));18console.log("Index of 4:", binarySearch(nums, 4));Код Binary Search на Java
Java
1public class Main {2 static int binarySearch(int[] a, int target) {3 int lo = 0;4 int hi = a.length - 1;5 while (lo <= hi) {6 int mid = (lo + hi) / 2;7 if (a[mid] == target) return mid;8 if (a[mid] < target) {9 lo = mid + 1; // search the right half10 } else {11 hi = mid - 1; // search the left half12 }13 }14 return -1;15 }16
17 public static void main(String[] args) {18 int[] nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted19 System.out.println("Index of 5: " + binarySearch(nums, 5));20 System.out.println("Index of 4: " + binarySearch(nums, 4));21 }22}Код Binary Search на C++
C++
1#include <iostream>2#include <vector>3
4int binarySearch(const std::vector<int>& a, int target) {5 int lo = 0;6 int hi = static_cast<int>(a.size()) - 1;7 while (lo <= hi) {8 int mid = lo + (hi - lo) / 2;9 if (a[mid] == target) return mid;10 if (a[mid] < target) {11 lo = mid + 1; // search the right half12 } else {13 hi = mid - 1; // search the left half14 }15 }16 return -1;17}18
19int main() {20 std::vector<int> nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted21 std::cout << "Index of 5: " << binarySearch(nums, 5) << "\n";22 std::cout << "Index of 4: " << binarySearch(nums, 4) << "\n";23 return 0;24}Код Binary Search на C
C
1#include <stdio.h>2
3int binary_search(const int a[], int n, int target) {4 int lo = 0;5 int hi = n - 1;6 while (lo <= hi) {7 int mid = lo + (hi - lo) / 2;8 if (a[mid] == target) return mid;9 if (a[mid] < target) {10 lo = mid + 1; /* search the right half */11 } else {12 hi = mid - 1; /* search the left half */13 }14 }15 return -1;16}17
18int main(void) {19 int nums[] = {1, 2, 3, 5, 7, 8, 9}; /* must be sorted */20 int n = sizeof(nums) / sizeof(nums[0]);21 printf("Index of 5: %d\n", binary_search(nums, n, 5));22 printf("Index of 4: %d\n", binary_search(nums, n, 4));23 return 0;24}Код Binary Search на Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74// The array must be sorted for binary search5nums[1] ← 16nums[2] ← 27nums[3] ← 38nums[4] ← 59nums[5] ← 710nums[6] ← 811nums[7] ← 912
13FUNCTION binarySearch(target : INTEGER) RETURNS INTEGER14 DECLARE lo : INTEGER15 DECLARE hi : INTEGER16 DECLARE mid : INTEGER17 lo ← 118 hi ← n19 WHILE lo <= hi DO20 mid ← (lo + hi) DIV 221 IF nums[mid] = target THEN22 RETURN mid23 ENDIF24 IF nums[mid] < target THEN25 // Target is larger — search the right half26 lo ← mid + 127 ELSE28 // Target is smaller — search the left half29 hi ← mid - 130 ENDIF31 ENDWHILE32 RETURN -133ENDFUNCTION34
35OUTPUT "Index of 5 is ", binarySearch(5)36OUTPUT "Index of 4 is ", binarySearch(4)Вопросы и ответы о бинарном поиске
Какова временная сложность бинарного поиска?
O(log n) в среднем и худшем случаях, потому что каждое сравнение делит оставшееся окно поиска пополам, и O(1) в лучшем случае, когда первый же средний элемент оказывается целью. Итеративная версия использует O(1) дополнительной памяти.Почему бинарному поиску нужен отсортированный массив?
Шаг деления пополам опирается на порядок: сравнение цели со средним элементом говорит, какую половину отбросить, только если всё слева от середины меньше, а всё справа — больше. Для неотсортированных данных этот вывод неверен — используйте линейный поиск или сначала отсортируйте.
В чём разница между бинарным и линейным поиском?
Линейный поиск просматривает элементы по одному (
O(n)) и работает с любым массивом; бинарный поиск делит пополам окно поиска в отсортированном массиве (O(log n)), но требует отсортированного входа. Для горстки элементов разница ничтожна — в масштабе бинарный поиск выигрывает с большим отрывом.Сколько сравнений нужно бинарному поиску?
Не более примерно
log2(n) + 1: 10 сравнений покрывают 1 000 элементов, 20 сравнений — 1 000 000. Именно этот логарифмический рост делает его поиском по умолчанию для отсортированных данных.В чём классическая ошибка переполнения в бинарном поиске?
Вычисление середины как
(lo + hi) / 2 может переполнить целые числа фиксированного размера, когда lo + hi превышает максимум типа. Безопасная форма — mid = lo + (hi - lo) / 2. В Python это не имеет значения (целые числа произвольной точности), но в Java/C/C++ это реальная и знаменитая ошибка.Бинарный поиск — это то же самое, что двоичное дерево поиска?
Их объединяет идея деления пополам, но структура различается: бинарный поиск — это алгоритм на отсортированном массиве, а двоичное дерево поиска — связная структура данных, которая хранит ключи упорядоченными, так что поиск на каждом узле спускается влево или вправо.
Связанные ресурсы
Больше визуализаций
