Поиск эффективного алгоритма двоичного поиска на C

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

Стандартная библиотека C предоставляет std::binary_search в заголовке , но это только возвращает логическое значение. Как отметил задавший вопрос, это может расстраивать в ситуациях, когда желательна скорость двоичного поиска, а данные отсортированы.

К счастью, существуют альтернативные реализации, которые предлагают желаемую функциональность. Одним из популярных вариантов является использование специального алгоритма, использующего функции std::lower_bound, std::upper_bound или std::equal_range. Вот упрощенная версия такой реализации:

template
Iter binary_find(Iter begin, Iter end, T val) {
    // Determine the lower bound using binary search
    Iter i = std::lower_bound(begin, end, val);

    // If the element is found, return the iterator to it
    if (i != end && !(val 
В качестве альтернативы можно использовать std::set, который гарантирует упорядочивание элементов и предоставляет метод find, который возвращает итератор к нужному элементу. Однако важно учитывать, совместимы ли требования с использованием набора, особенно в тех случаях, когда необходимо хранить несколько экземпляров одного и того же элемента.