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

106

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.

Robert Gould
fuente
2
Con respecto a la edición: es por eso que std :: equal_range es la solución. De lo contrario, tendrá que probar la igualdad (o la equivalencia para ser más)
Luc Hermitte
Debe probar la igualdad después de usar (inferior / superior) _bound (consulte la respuesta a continuación).
Luc Touraille
La documentación de lower_bound y upper_bound indica que el rango debe ser ordenado, y debido a esto se pueden implementar como búsqueda binaria.
vividos
@vividos, ¡hurra! ¡Encontraste la documentación que necesitaba conocer! ¡Gracias!
Robert Gould
Robert, los algoritmos lower / upper_bound / equal_range no funcionan con rangos sin clasificar. Tiene suerte de verlos trabajar con la muestra de elementos que tomó.
Luc Hermitte

Respuestas:

97

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).

Luc Touraille
fuente
sí, esto funciona, y tengo una implementación similar en este momento, sin embargo, es una implementación "ingenua", en el sentido de que no está haciendo uso del contexto de la situación, en este caso datos ordenados.
Robert Gould
5
Realmente no entiendo su comentario, ya que lower_bound solo se puede usar en datos ordenados. La complejidad es menor que usar buscar (ver editar).
Luc Touraille
4
Para complementar la respuesta de Luc, consulte el artículo clásico de Matt Austern Por qué no debería usar el conjunto y Qué debería usar en su lugar (Informe de C ++ 12: 4, abril de 2000) para comprender por qué la búsqueda binaria con vectores ordenados suele ser preferible a std :: set , que es un contenedor asociativo basado en árboles.
ZunTzu
16
¡No lo use *i == val! Más bien use !(val < *i). La razón es que lower_boundutiliza <, no ==( Tes decir, ni siquiera se requiere que sea comparable en igualdad). (Consulte el STL efectivo de Scott Meyers para obtener una explicación de la diferencia entre igualdad y equivalencia .)
gx_
1
@ CanKavaklıoğlu No hay ningún elemento ubicado en end. Los rangos en la biblioteca estándar de C ++ se representan con intervalos semiabiertos: el iterador final "apunta" después del último elemento. Como tal, puede ser devuelto por algoritmos para indicar que no se encontró ningún valor.
Luc Touraille
9

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

Luc Hermitte
fuente
Según cplusplus.com/reference/algorithm/equal_range, el costo de std :: equal_range es aproximadamente el doble de std :: lower_bound. Parece que envuelve una llamada a std :: lower_bound y una llamada a std :: upper_bound. Si sabe que sus datos no tienen duplicados, entonces eso es excesivo y std :: lower_bound (como se demuestra en la respuesta superior) es la mejor opción.
Bruce Dawson
@BruceDawson: cplusplus.com solo proporciona una implementación de referencia para especificar el comportamiento ; para una implementación real, puede consultar su biblioteca estándar favorita. Por ejemplo, en llvm.org/svn/llvm-project/libcxx/trunk/include/algorithm podemos ver que las llamadas a lower_bound y upper_bound se realizan en intervalos disjuntos (después de una búsqueda binaria manual). Dicho esto, es probable que sea más caro, especialmente en rangos con múltiples valores coincidentes.
Matthieu M.
6

Hay un conjunto de ellos:

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

Buscar:

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.

Martin York
fuente
3
binary_search no devuelve un iterador como mencioné anteriormente, por eso estoy buscando una alternativa.
Robert Gould
1
Sí, lo sé. Pero encaja en el conjunto de algoritmos de búsqueda binaria. Así que es bueno que otros lo sepan.
Martin York
8
binary_search, como tantas otras cosas en STL, tiene un nombre incorrecto. Odio eso. Probar la existencia no es lo mismo que buscar algo.
OregonGhost
2
Estas funciones de búsqueda binaria no son útiles en caso de que desee conocer el índice del elemento que está buscando. Tengo que escribir mi propia función recursiva para esta tarea. Espero que esta plantilla <class T> int bindary_search (const T & item) se agregue a la próxima versión de C ++.
Kemin Zhou
3

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.

ZunTzu
fuente
1
Buen enlace; y también un buen enlace en el enlace: lafstern.org/matt/col1.pdf , que describe cómo las búsquedas implementadas con un vector ordenado, en lugar de un conjunto (aunque ambos son log (N)), tienen constantes de proporcionalidad significativamente mejores y son ~ dos veces más rápido (la desventaja es un mayor tiempo de INSERCIÓN).
Dan Nissenbaum
2

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

trozen
fuente
Puedo pensar en dos razones por las que esto no está en la biblioteca estándar: piensan que es fácil de implementar, pero la razón principal es probablemente que puede requerir una versión inversa de operator () () si el valor no es intercambiable con * primero.
user877329
1

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 .

Ley y
fuente
1
Desafortunadamente, este algoritmo no es compatible con los contenedores STL.
bartolo-otrit
0

std :: lower_bound () :)

moogs
fuente
OP: "hasta el momento lower_bound y upper_bound fallan, porque ..."
underscore_d
0
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.

Siddharth Kumar Shukla
fuente
1
Es bueno tener código, pero podría mejorar la respuesta proporcionando una breve explicación de cómo funciona para las personas que son nuevas en el idioma.
Taegost
Alguien marcó incorrectamente tu publicación como de baja calidad . Una respuesta de solo código no es de baja calidad . ¿Intenta responder la pregunta? De lo contrario, marque como 'no es una respuesta' o recomiende la eliminación (si está en la cola de revisión). b) ¿Es técnicamente incorrecto? Votar en contra o comentar.
Wai Ha Lee
0

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;

}
Michele Belotti
fuente