Введение
Бинарный поиск — это фундаментальная техника, используемая для эффективного нахождения элемента или оптимального значения, когда ответ ведёт себя монотонно.
Предположим, у нас есть отсортированный массив
Бинарный поиск — это фундаментальная техника, используемая для эффективного нахождения элемента или оптимального значения, когда ответ ведёт себя монотонно.
Предположим, у нас есть отсортированный массив
Решите эти задачи, чтобы закрепить материал урока:
Решите эти внешние задачи (например, из Codeforces) чтобы закрепить материал урока:
и мы хотим найти позицию значения , то есть индекс такой, что
Простое решение — просканировать массив слева направо.
Это работает за время .
Однако, поскольку массив отсортирован, мы можем сделать гораздо лучше. Используя бинарный поиск, мы можем решить задачу за время .
Основная идея — поддерживать интервал , который всё ещё может содержать ответ, многократно делить его на две половины и отбрасывать половину, в которой ответа быть не может.
Теперь мы опишем стандартный итеративный бинарный поиск, который возвращает индекс такой, что a[i] = x, или -1, если отсутствует.
В начале ответ, если он существует, должен лежать в интервале:
Затем мы повторяем следующий процесс.
Интервал содержит только одну позицию.
Мы делим интервал на две части.
Пусть
Тогда интервал делится на:
Теперь есть две возможности:
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;
}