Давайте обсудим интуицию, стоящую за бинарным поиском. Вы когда-нибудь искали номер страницы в книге? Если это так, вы, вероятно, использовали технику, начиная с середины и медленно двигаясь вперед или назад, пока не нашли нужную страницу. В бинарном поиске (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).

В заключение, бинарный поиск — это мощный алгоритм, который можно использовать в различных ситуациях. Правильно реализовав его, мы можем значительно уменьшить временную сложность нашего кода.

Мир вон😊