Как работает бинарный поиск и почему это важный алгоритм
Бинарный поиск — это фундаментальная техника, используемая для эффективного нахождения элемента или оптимального значения, когда ответ ведёт себя ``монотонно''.
Предположим, у нас есть отсортированный массив , и мы хотим найти позицию значения , т.е. такой индекс , что .
Наивное решение — просканировать массив:
Это работает за время .
Однако, поскольку массив отсортирован, мы можем сделать намного лучше: использовать бинарный поиск и получить время : мы поддерживаем интервал , который точно содержит ответ (если он существует), многократно делим его на две половины и отбрасываем половину, в которой ответа быть не может.
Теперь мы опишем стандартный итеративный бинарный поиск, который возвращает любой индекс такой, что , или , если отсутствует.
Инициализируем диапазон ответа, т.е. интервал , где лежит ответ (). В самом начале .
Затем у нас есть два случая:
int find_linear(int x) {
for (int i = 1; i <= n; i++) {
if (a[i] == x) {
return i;
}
}
return -1; // если x не существует в массиве
}
int binary_search_any(int x) {
int l = 1;
int r = n;
while (l < r) {
int m = (l + r) / 2;
if (a[m] < x) {
l = m + 1;
} else {
r = m;
}
}
if (a[l] == x) {
return l;
}
return -1;
}