Сложную задачу часто имеет смысл разбить на более маленькие, более простые задачи. Если задача разбивается на подзадачи - нужно применить рекурсию. Одним из таких алгоритмов является двоичный поиск.

Как работает двоичный поиск?

Этот алгоритм позволяет быстро найти элемент q в отсортированном массиве S. Мы сравниваем q с серединным элементом массива S. Если q больше этого элемента, то дальше работаем только с правой частью массива (от середины и до конца), а левую отбрасываем. Если q меньше серединного элемента, то работаем только с левой частью массива( от начала и до середины), а правую отбрасываем. Рекурсивно повторяем эти действия и таким образом находим q.

Такой подход позволяет намного быстрее найти нужный элемент(ключ) в массиве, чем при последовательном поиске.

Пример кода

// low - нижняя граница(она же левая) списка(массива или другого хранилища данных)
// high - верхняя граница( она же правая)
//key - искомый объект(число, строка и тд и тп)
int bin_search(item_type s[], item_type key, int low, int high) {
    int middle = (low + hight) / 2; //середина
    if (low > high) { // проверка корректности нижней и верхней границы
        return -1;
    }
    if (s[middle] == key) {//если середина и есть искомый объект
        return(middle);
    }
    if (s[middle] > key) {
        return(bin_search(s, key, low, middle - 1));// middle - 1 потому что середина уже учлась выше
    }
    else {
        return(bin_search(s, key, middle + 1, high));
    }
}

Примеры применения

Двоичный поиск идеально подходит для поиска корней уравнения f(x)=0. Взять два числа t и s для которых f(t) и f(s) будут иметь разные знаки. Для непрерывной функции корень будет находиться в интервале между t и s. Для поиска корня здесь отлично помогает двоичный поиск.

Литература

[ Скиена 2022 с. 181]