Wo kann ich einen "nützlichen" C++ - Binärsuchalgorithmus bekommen?

Question

Ich brauche einen binären Suchalgorithmus, der kompatibel ist mit den C++ STL-Containern, etwa std::binary_search in der Standard-Bibliothek <algorithm> Header, aber ich brauche es den Iterator, der auf das Ergebnis verweist, nicht eine einfache Boolean sagen mir, ob das Element existiert.

(Auf einer Seite zur Kenntnis, was zum Teufel das Standard-Komitee Denken war, als sie die API für binary_search ?! definiert)

Mein hier Hauptanliegen ist, dass ich die Geschwindigkeit einer binären Suche benötigen, so dass, obwohl ich kann die Daten mit anderen Algorithmen finden, wie unten erwähnt, möchte ich die Tatsache nutzen, dass meine Daten sortiert sind, um die Vorteile einer binären Suche, nicht eine lineare Suche zu erhalten.

bisher lower_bound und upper_bound fehlschlagen, wenn das Datum fehlt:

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

Hinweis: Ich bin auch in Ordnung unter Verwendung eines Algorithmus, der dem std-Namespace gehört nicht so lange seine kompatibel mit Behälter. Wie zum Beispiel, boost::binary_search.

Answer 1

Es gibt keine solche Funktionen, aber Sie können eine einfache Verwendung std::lower_bound, std::upper_bound oder std::equal_range schreiben.

Eine einfache Implementierung

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 
} 

Eine andere Lösung, die eine std::set, die die Reihenfolge der Elemente gewährleistet und ein Verfahren iterator find(T key) bietet wäre verwenden könnte, die einen Iterator auf das gegebene Element zurückgibt. Ihre Anforderungen sind jedoch möglicherweise nicht mit der Verwendung eines Satzes kompatibel (z. B. wenn Sie das gleiche Element mehrmals speichern müssen).

Answer 2

Sie sollten sich std::equal_range ansehen. Es wird ein Paar Iteratoren auf den Bereich aller Ergebnisse zurückgeben.

Answer 3

Es gibt eine Reihe von ihnen:

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

Suchen nach:

• lower_bound
• upper_bound
• equal_range
• binary_search

Auf einem separaten Hinweis:

Sie wurden wahrscheinlich denken, dass die Behälter der Suche mehr als ein Ergebnis bezeichnen könnte. Aber in den seltenen Fällen, in denen Sie nur auf Existenz testen müssen, wäre eine optimierte Version auch schön.

Answer 4

std :: lower_bound() :)

Answer 5

Aktivieren Sie diese Funktion, qBinaryFind:

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

Führt eine binäre Suche des Bereichs [begin, end) und gibt die Position eines Auftretens des Wertes. Wenn dort keine Vorkommen von Wert sind, gibt Ende zurück.

Die Artikel im Bereich [Anfang, Ende] müssen aufsteigend sortiert sein; siehe qSort().

Wenn es viele Vorkommen des gleichen Werts gibt, könnte einer von ihnen zurückgegeben werden. Verwenden Sie qLowerBound() oder qUpperBound(), wenn Sie feinere Kontrolle benötigen.

Beispiel:

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) 

Die Funktion wird im <QtAlgorithms> Header enthalten, der ein Teil der Qt Bibliothek ist.

Answer 6

Wenn std :: lower_bound für Sie zu niedrig ist, sollten Sie boost::container::flat_multiset überprüfen. Es ist ein Drop-in-Ersatz für std :: multiset als sortierten Vektor mit binärer Suche implementiert.

Answer 7

Eine Lösung, die Position innerhalb des Bereichs zurückkehren könnte so sein, nur mit Operationen auf Iteratoren (es sollte funktionieren, auch wenn Iterator nicht Arithmetik der Fall ist):

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

Beispiel: ein Array Betrachten, A = [1,2,3,4,5,6,7,8,9] Angenommen, Sie möchten den Index von 3 suchen Zunächst Start = 0 und Ende = 9-1 = 8 Jetzt, seit dem Start < = Ende; Mitte = 4; (Array [Mitte] welches 5 ist!) = 3 Jetzt liegt 3 links von der Mitte als kleiner als 5. Daher suchen wir nur den linken Teil des Arrays Daher jetzt Start = 0 und Ende = 3 ; mid = 2. Seit array [mid] == 3 haben wir die Nummer gefunden, nach der wir gesucht haben. Daher geben wir seinen Index zurück, der gleich der Mitte ist.