Où puis-je trouver un algorithme de recherche binaire C ++ «utile»?

J'ai besoin d'un algorithme de recherche binaire compatible avec les conteneurs C ++ STL, quelque chose comme std::binary_searchdans l'en- <algorithm>tête de la bibliothèque standard , mais j'en ai besoin pour renvoyer l'itérateur qui pointe sur le résultat, pas un simple booléen me disant si l'élément existe.

(En passant, à quoi pensait le comité standard quand ils ont défini l'API pour binary_search?!)

Ma principale préoccupation ici est que j'ai besoin de la vitesse d'une recherche binaire, donc bien que je puisse trouver les données avec d'autres algorithmes, comme mentionné ci-dessous, je veux profiter du fait que mes données sont triées pour bénéficier des avantages d'un binaire recherche, pas une recherche linéaire.

jusqu'ici lower_boundet upper_boundéchouer si la donnée est manquante:

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

Remarque: je suis également très bien en utilisant un algorithme qui n'appartient pas à l'espace de noms std tant qu'il est compatible avec les conteneurs. Comme, par exemple, boost::binary_search.

Il n'y a pas de telles fonctions, mais vous pouvez en écrire une simple en utilisant std::lower_bound, std::upper_boundou std::equal_range.

Une implémentation simple pourrait être

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
}

Une autre solution serait d'utiliser un std::set , qui garantit l'ordre des éléments et fournit une méthode iterator find(T key)qui retourne un itérateur à l'élément donné. Cependant, vos exigences peuvent ne pas être compatibles avec l'utilisation d'un ensemble (par exemple, si vous devez stocker le même élément plusieurs fois).

Vous devriez y jeter un œil std::equal_range. Il renverra une paire d'itérateurs dans la plage de tous les résultats.

Il y en a un ensemble:

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

Rechercher:

• borne inférieure
• borne_ supérieure
• intervalle_égal
• recherche binaire

Sur une note distincte:

Ils pensaient probablement que la recherche de conteneurs pouvait aboutir à plus d'un résultat. Mais dans les rares cas où vous avez juste besoin de tester l'existence, une version optimisée serait également bien.

Si std :: lower_bound est trop bas à votre goût, vous pouvez vérifier boost :: container :: flat_multiset . Il s'agit d'un remplacement de std :: multiset implémenté en tant que vecteur trié à l'aide de la recherche binaire.

L'implémentation la plus courte, se demandant pourquoi elle n'est pas incluse dans la bibliothèque standard:

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;
}

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

Vérifiez cette fonction, qBinaryFind :

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

Effectue une recherche binaire de la plage [début, fin) et renvoie la position d'une occurrence de valeur. S'il n'y a pas d'occurrences de valeur, renvoie end.

Les éléments de la plage [début, fin) doivent être triés par ordre croissant; voir qSort ().

S'il existe de nombreuses occurrences de la même valeur, n'importe laquelle d'entre elles peut être renvoyée. Utilisez qLowerBound () ou qUpperBound () si vous avez besoin d'un contrôle plus fin.

Exemple:

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 fonction est incluse dans l'en- <QtAlgorithms>tête qui fait partie de la bibliothèque Qt .

std :: borne_ inférieure () :)

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;
}

Exemple: Prenons un tableau, A = [1,2,3,4,5,6,7,8,9] Supposons que vous souhaitiez rechercher l'index de 3 Initialement, start = 0 et end = 9-1 = 8 Now , puisque début <= fin; milieu = 4; (tableau [milieu] qui vaut 5)! = 3 Maintenant, 3 se trouve à gauche du milieu car il est plus petit que 5. Par conséquent, nous ne cherchons que la partie gauche du tableau. Par conséquent, maintenant start = 0 et end = 3; mid = 2. Depuis array [mid] == 3, nous avons donc obtenu le numéro que nous recherchions. Par conséquent, nous retournons son indice qui est égal à mid.

Une solution renvoyant la position à l'intérieur de la plage pourrait être comme ceci, en utilisant uniquement des opérations sur les itérateurs (cela devrait fonctionner même si l'itérateur ne fait pas d'arithmétique):

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;

}