Búsqueda de un algoritmo de búsqueda binaria eficiente en C

Los programadores a menudo buscan implementar algoritmos de búsqueda binaria eficientes que proporcionen los beneficios de la complejidad del tiempo logarítmico . Un requisito común es que el algoritmo devuelva un iterador que apunte al resultado de la búsqueda en lugar de un simple booleano que indique su existencia.

La biblioteca estándar de C proporciona std::binary_search en el encabezado , pero solo devuelve un booleano. Como señaló el autor de la pregunta, esto puede resultar frustrante en situaciones en las que se desea la velocidad de una búsqueda binaria y se sabe que los datos están ordenados.

Afortunadamente, existen implementaciones alternativas disponibles que ofrecen la funcionalidad deseada. Una opción popular es utilizar un algoritmo personalizado que aproveche las funciones std::lower_bound, std::upper_bound o std::equal_range. Aquí hay una versión simplificada de dicha implementación:

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 
Como alternativa, se puede utilizar un std::set, que garantiza el orden de los elementos y proporciona el método de búsqueda que devuelve un iterador al elemento deseado. Sin embargo, es importante considerar si los requisitos son compatibles con el uso de un conjunto, particularmente en los casos en los que es necesario almacenar varias instancias del mismo elemento.