Où puis-je obtenir un algorithme de recherche binaire "utile" C ++?

Question

J'ai besoin d'un binaire de l'algorithme de recherche qui est compatible avec la norme C++ conteneurs, quelque chose comme std::binary_search dans la bibliothèque standard de l' <algorithm> - tête, mais à la différence de std::binary_search, j'en ai besoin pour retourner l'itérateur qui pointe le résultat, non pas d'une simple booléen me dire si l'élément existe

(Sur une note de côté, ce que l'enfer était le comité des normes de la pensée quand ils ont défini l'API pour binary_search!!!)

Edit: Ma principale préoccupation ici est que j'ai besoin de la vitesse d'une binaire de recherche, si bien que je peux trouver les données avec d'autres algorithmes, comme mentionné ci-dessous, je veux profiter de mes données sont déjà triées pour obtenir les avantages d'une binaire de recherche, et pas seulement de la recherche.

jusqu'à présent lower_bound et upper_bound échouer, parce que 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

Aussi, je doute vraiment lower_bound et upper_bound sont mis en œuvre comme binary_searches, parce qu'ils fonctionnent aussi bien avec des données non triées, et il n'existe aucun moyen de fournir des informations à travers les arguments ou les politiques. Ok d'abord mentionné par vividos, elles NE nécessitent des données triées, ce qui signifie qu'ils SONT binaires de recherche, de sorte que le monde est bon à nouveau :)

Note: je suis aussi fine à l'aide d'un algorithme qui n'appartient pas à l'espace de noms std aussi longue que il est compatible avec les conteneurs. Aime dire boost::binary_search ou quelque chose

Answer 1

Il n'y a pas de telles fonctions, mais vous pouvez écrire un simple à l'aide de std::lower_bound, std::upper_bound ou std::equal_range.

Une simple mise en œuvre 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, ce qui garantit l'ordre des éléments et fournit une méthode iterator find(T key) qui renvoie un itérateur vers l'élément donné. Cependant vos exigences ne sont pas compatibles avec l'utilisation d'un ensemble (par exemple, si vous avez besoin de stocker le même élément plusieurs fois).

Answer 2

Vous devriez jeter un oeil à std :: equal_range. Cela retournera une paire d'itérateurs à la plage de tous les résultats.

Answer 3

Il y a un ensemble d'entre eux:

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

Recherche pour:

• lower_bound
• upper_bound
• equal_range
• binary_search

Sur une note séparée:

Ils étaient sans doute penser que la recherche de conteneurs pourrait à terme de plus d'un résultat. Mais pour les quelques fois où vous avez juste besoin de tester l'existence d'une version optimisée serait bien aussi.

Answer 4

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

Answer 5

std :: lower_bound () :)