Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.
Частным случаем двоичного поиска является метод бисекции, который применяется для поиска корней заданной непрерывной функции на заданном отрезке.
Пример кода на языке программирования Си для поиска элемента x в массиве a[n], отсортированного в возрастающем порядке: [скрыть] Код на C #include <stdio.h>
struct Result { size_t pos; int isFound; };
struct Result makeResult(size_t pos, int isFound) { struct Result r; r.pos = pos; r.isFound = isFound; return r; }
/* Макросы, означающие «найдено в позиции i» и «не найдено, если нужно * вставить со сдвигом, то в позицию i». */ #define FOUND(i) makeResult(i, 1) #define NOTFOUND(i) makeResult(i, 0)
struct Result binarySearch(size_t n, int a[], int x) { /* Номер первого элемента в массиве */ size_t first = 0; /* Номер элемента в массиве, СЛЕДУЮЩЕГО ЗА последним */ size_t last = n;
/* Начальная проверка, которую, в принципе, можно опустить — но тогда см. ниже! */ if (n == 0) { /* массив пуст */ return NOTFOUND(0); } else if (a[0] > x) { /* искомый элемент меньше всех в массиве */ return NOTFOUND(0); } else if (a[n - 1] < x) { /* искомый элемент больше всех в массиве */ return NOTFOUND(n); }
/* Если просматриваемый участок непустой, first < last */ while (first < last) { /* ВНИМАНИЕ! В отличие от более простого (first + last) / 2, * этот код устойчив к переполнениям. * * Если first и last знаковые, возможен код: * ((unsigned)first + (unsigned)last) >> 1. * Соотвественно в Java: (first + last) >>> 1. */ size_t mid = first + (last - first) / 2;
if (x <= a[mid]) last = mid; else first = mid + 1; }
/* Если условный оператор if (n == 0) и т.д. в начале опущен - * значит, тут раскомментировать! */ if (/* last < n && */ a[last] == x) { /* Искомый элемент найден. last - искомый индекс */ return FOUND(last); } else { /* Искомый элемент не найден. Но если вам вдруг надо его * вставить со сдвигом, то его место - last. */ return NOTFOUND(last); } }
int main() { int a[] = { 1, 3, 5, 7, 9 }; struct Result r = binarySearch(5, a, 12); /* Вторая подстановка соответствует соглашениям Windows; на Unix %zu */ printf("%s at %Iu\n", r.isFound ? "Found" : "Not found", r.pos); return 0; } [скрыть] Код на C++ #include <iostream>
using namespace std;
int binfind(int a[], int x, int left, int right) { if (left > right) { return -1; }
int mid = (left + right) / 2;
if (a[mid] == x) return mid; if (a[mid] < x) return binfind(a, x, mid + 1, right); if (a[mid] > x) return binfind(a, x, left, mid - 1); }
int main() { int N = 15; // Размер массива. int a[N];
int x = 6; // Искомый элемент. for (int i = 0; i < N; ++i) { a[i] = i; }
cout << binfind(a, x, 0, N) << endl;
return 0; }
Несмотря на то, что код достаточно прост, в нём есть несколько ловушек. Что будет, если first и last по отдельности умещаются в свой тип, а first+last — нет?[] Будет ли работать на пустом массиве (n=0)? Способен ли код находить отсутствующие значения? У некоторых программистов написанный «с листа» двоичный поиск в такой ситуации зацикливается — и они этого не осознают, пока тестирование не даст ошибку. Способен ли код найти первый и последний элемент? Возможна и обратная ошибка — выход за границы массива, если x задать слишком большим или слишком маленьким. Иногда требуется, чтобы, если x в цепочке существует в нескольких экземплярах, находило не любой, а обязательно первый (как вариант: последний; либо вообще не x, а следующий за ним элемент).[] Данная версия кода в такой ситуации находит первый из равных.
Учёный Йон Бентли утверждает, что 90 % студентов, разрабатывая двоичный поиск, забывают учесть какое-либо из этих требований. И даже в код, написанный самим Йоном и ходивший из книги в книгу, вкралась ошибка: код не стоек к переполнениям.
Практические приложения метода двоичного поиска разнообразны: Широкое распространение в информатике применительно к поиску в структурах данных. Например, поиск в массивах данных осуществляется по ключу, присвоенному каждому из элементов массива (в простейшем случае сам элемент является ключом). Также его применяют в качестве численного метода для нахождения приближённого решения уравнений (см. Метод бисекции). Метод используется для нахождения экстремума целевой функции и в этом случае является методом условной одномерной оптимизации. Когда функция имеет вещественный аргумент, найти решение с точностью до можно за время . Когда аргумент дискретен, и изначально лежит на отрезке длины N, поиск решения займёт времени. Наконец, для поиска экстремума, скажем, для определённости минимума, на очередном шаге отбрасывается тот из концов рассматриваемого отрезка, значение в котором максимально.
