Давайте обсудим интуицию, стоящую за бинарным поиском. Вы когда-нибудь искали номер страницы в книге? Если это так, вы, вероятно, использовали технику, начиная с середины и медленно двигаясь вперед или назад, пока не нашли нужную страницу. В бинарном поиске (BS) место, которое мы ищем, называется пространством поиска, а средний элемент пространства поиска называется «серединой» алгоритма. Например, в книге из 100 страниц область поиска — это страницы книги, а середина — 50-я страница.
Люди часто думают, что бинарный поиск можно реализовать только в отсортированном массиве, но это не так. BS можно использовать для любого возрастающего или убывающего количества, а также для последовательности, которая переходит от ложного к истинному. В этих случаях мы можем использовать BS, чтобы найти наше решение.
Теперь поговорим о реализации БС. Самая захватывающая часть — это ее реализация! Например, возьмем отсортированный массив чисел:
число = [12, 23, 45, 89, 90, 90], n=6
Мы определяем некоторые параметры, такие как нижняя граница, верхняя граница и средний элемент, которые обычно представляются как l, r и mid. Алгоритм работает, отбрасывая половину массива, которая не содержит нужного значения, точно так же, как когда мы находим страницу в книге.
Сначала мы вычисляем середину массива и сравниваем ее с целевым значением. На основе сравнения мы решаем, будет ли ответ падать на левую или правую сторону середины. Если мы находим элемент с левой стороны, мы полностью отбрасываем правую сторону и движемся вперед.
Вот реализация алгоритма:
int binary_search(int num[], int l, int r, int x) { while (l <= r) { // mid is alway calculated after each iteration int m = l + (r - l) / 2; // Check if x is present at mid, if present return if (num[m] == x) return m; // If x greater, ignore left half if (num[m] < x) l = m + 1; // If x is smaller, ignore right half else r = m - 1; } // if we reach here, then element was // not present return -1; }
Сложность времени и пространства
С точки зрения временной сложности наихудший сценарий — O(logN), где N — количество элементов в массиве. Пространственная сложность алгоритма составляет O(1).
В заключение, бинарный поиск — это мощный алгоритм, который можно использовать в различных ситуациях. Правильно реализовав его, мы можем значительно уменьшить временную сложность нашего кода.