¿Dónde puedo conseguir un algoritmo de búsqueda binaria C ++ "útil"?

Necesito un algoritmo de búsqueda binaria que sea compatible con los contenedores C ++ STL, algo así como std::binary_searchen el <algorithm>encabezado de la biblioteca estándar , pero lo necesito para devolver el iterador que apunta al resultado, no un simple booleano que me diga si el elemento existe.

(En una nota al margen, ¿qué diablos estaba pensando el comité estándar cuando definieron la API para binary_search?)

Mi principal preocupación aquí es que necesito la velocidad de una búsqueda binaria, por lo que, aunque puedo encontrar los datos con otros algoritmos, como se menciona a continuación, quiero aprovechar el hecho de que mis datos están ordenados para obtener los beneficios de un binario. búsqueda, no una búsqueda lineal.

hasta ahora lower_boundy upper_boundfallar si falta el dato:

//lousy pseudo code
vector(1,2,3,4,6,7,8,9,0) //notice no 5
iter = lower_bound_or_upper_bound(start,end,5)
iter != 5 && iter !=end //not returning end as usual, instead it'll return 4 or 6

Nota: también estoy bien usando un algoritmo que no pertenece al espacio de nombres estándar siempre que sea compatible con los contenedores. Como, por ejemplo, boost::binary_search.

No existen tales funciones, pero puede escribir una simple usando std::lower_bound, std::upper_boundo std::equal_range.

Una implementación simple podría ser

template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val)
{
    // Finds the lower bound in at most log(last - first) + 1 comparisons
    Iter i = std::lower_bound(begin, end, val);

    if (i != end && !(val < *i))
        return i; // found
    else
        return end; // not found
}

Otra solución sería utilizar a std::set, que garantiza el orden de los elementos y proporciona un método iterator find(T key)que devuelve un iterador al elemento dado. Sin embargo, es posible que sus requisitos no sean compatibles con el uso de un conjunto (por ejemplo, si necesita almacenar el mismo elemento varias veces).

Deberías echarle un vistazo std::equal_range. Devolverá un par de iteradores al rango de todos los resultados.

Hay un conjunto de ellos:

http://www.sgi.com/tech/stl/table_of_contents.html

Buscar:

• límite inferior
• upper_bound
• igual_rango
• búsqueda binaria

En una nota aparte:

Probablemente pensaban que la búsqueda de contenedores podría dar lugar a más de un resultado. Pero en las raras ocasiones en las que solo necesita probar la existencia, una versión optimizada también sería buena.

Si std :: lower_bound es de un nivel demasiado bajo para su gusto, es posible que desee verificar boost :: container :: flat_multiset . Es un reemplazo directo para std :: multiset implementado como un vector ordenado usando búsqueda binaria.

La implementación más corta, preguntándose por qué no está incluida en la biblioteca estándar:

template<class ForwardIt, class T, class Compare=std::less<>>
ForwardIt binary_find(ForwardIt first, ForwardIt last, const T& value, Compare comp={})
{
    // Note: BOTH type T and the type after ForwardIt is dereferenced 
    // must be implicitly convertible to BOTH Type1 and Type2, used in Compare. 
    // This is stricter than lower_bound requirement (see above)

    first = std::lower_bound(first, last, value, comp);
    return first != last && !comp(value, *first) ? first : last;
}

De https://en.cppreference.com/w/cpp/algorithm/lower_bound

Marque esta función, qBinaryFind :

RandomAccessIterator qBinaryFind ( RandomAccessIterator begin, RandomAccessIterator end, const T & value )

Realiza una búsqueda binaria del rango [inicio, fin) y devuelve la posición de una ocurrencia de valor. Si no hay ocurrencias de valor, devuelve fin.

Los elementos del rango [inicio, fin) deben ordenarse en orden ascendente; consulte qSort ().

Si hay muchas apariciones del mismo valor, se puede devolver cualquiera de ellas. Utilice qLowerBound () o qUpperBound () si necesita un control más preciso.

Ejemplo:

QVector<int> vect;
 vect << 3 << 3 << 6 << 6 << 6 << 8;

 QVector<int>::iterator i =
         qBinaryFind(vect.begin(), vect.end(), 6);
 // i == vect.begin() + 2 (or 3 or 4)

La función está incluida en el <QtAlgorithms>encabezado, que es parte de la biblioteca Qt .

std :: lower_bound () :)

int BinarySearch(vector<int> array,int var)
{ 
    //array should be sorted in ascending order in this case  
    int start=0;
    int end=array.size()-1;
    while(start<=end){
        int mid=(start+end)/2;
        if(array[mid]==var){
            return mid;
        }
        else if(var<array[mid]){
            end=mid-1;
        }
        else{
            start=mid+1;
        }
    }
    return 0;
}

Ejemplo: Considere una matriz, A = [1,2,3,4,5,6,7,8,9] Suponga que desea buscar el índice de 3 Inicialmente, inicio = 0 y final = 9-1 = 8 Ahora , desde inicio <= final; mid = 4; (matriz [mid] que es 5)! = 3 Ahora, 3 se encuentra a la izquierda de mid ya que es menor que 5. Por lo tanto, solo buscamos en la parte izquierda de la matriz. Por lo tanto, ahora start = 0 y end = 3; mid = 2.Desde array [mid] == 3, obtuvimos el número que estábamos buscando. Por lo tanto, devolvemos su índice que es igual a mid.

Una solución que devuelva la posición dentro del rango podría ser así, usando solo operaciones en iteradores (debería funcionar incluso si el iterador no es aritmético):

template <class InputIterator, typename T>
size_t BinarySearchPos(InputIterator first, InputIterator last, const T& val)
{       
    const InputIterator beginIt = first;
    InputIterator element = first;
    size_t p = 0;
    size_t shift = 0;
    while((first <= last)) 
    {
        p = std::distance(beginIt, first);
        size_t u = std::distance(beginIt, last);
        size_t m = p + (u-p)/2;  // overflow safe (p+u)/2
        std::advance(element, m - shift);
        shift = m;
        if(*element == val) 
            return m; // value found at position  m
        if(val > *element)
            first = element++;
        else
            last  = element--;

    }
    // if you are here the value is not present in the list, 
    // however if there are the value should be at position u
    // (here p==u)
    return p;

}