lower - queue find c++

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

Question

Necesito un algoritmo de búsqueda binario que sea compatible con los contenedores C ++ STL, algo así como std::binary_search en el encabezado <algorithm> la biblioteca estándar, pero necesito devolver el iterador que apunta al resultado, no un simple booleano diciéndome si el elemento existe

(En una nota al margen, ¿qué demonios 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, así 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_bound y upper_bound fallan si falta el datum:

//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 contenedores. Como, digamos, boost::binary_search .

Answer 1

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

Answer 2

Hay un conjunto de ellos:

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

Buscar:

• lower_bound
• upper_bound
• equal_range
• binary_search

En una nota aparte:

Probablemente pensaban que buscar contenedores podría dar más de un resultado. Pero en la extraña ocasión en la que solo necesitas probar la existencia, una versión optimizada también sería agradable.

Answer 3

No existen tales funciones, pero puede escribir una simple usando std::lower_bound , std::upper_bound o 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 usar un 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, sus requisitos pueden no ser compatibles con el uso de un conjunto (por ejemplo, si necesita almacenar el mismo elemento varias veces).

Answer 4

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

Answer 5

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 tiene aritmética):

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)/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;

}

Answer 6

Verifica 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 el final.

Los elementos en el rango [inicio, fin] deben ordenarse en orden ascendente; ver qSort ().

Si hay muchas ocurrencias del mismo valor, cualquiera de ellas podría ser devuelto. Use 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> que forma parte de la biblioteca Qt .

Answer 7

std :: lower_bound () :)

Answer 8

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, start = 0 y end = 9-1 = 8 Now , desde el comienzo <= fin; mid = 4; (array [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 la parte izquierda de la matriz. Por lo tanto, ahora start = 0 y end = 3; mid = 2.Since array [mid] == 3, de ahí que obtuvimos el número que estábamos buscando. Por lo tanto, devolvemos su índice que es igual a mediados.