Wo kann ich einen "nützlichen" binären C ++ - Suchalgorithmus bekommen?

106

Ich benötige einen binären Suchalgorithmus, der mit den C ++ STL-Containern kompatibel ist, ähnlich wie std::binary_searchim <algorithm>Header der Standardbibliothek , aber ich brauche ihn, um den Iterator zurückzugeben, der auf das Ergebnis zeigt, und keinen einfachen Booleschen Wert, der mir sagt, ob das Element vorhanden ist.

(Nebenbei bemerkt, was zum Teufel hat das Standardkomitee gedacht, als es die API für binary_search definiert hat?!)

Mein Hauptanliegen hierbei ist, dass ich die Geschwindigkeit einer binären Suche benötige. Obwohl ich die Daten mit anderen Algorithmen finden kann, wie unten erwähnt, möchte ich die Tatsache nutzen, dass meine Daten sortiert sind, um die Vorteile einer binären Suche zu nutzen Suche, keine lineare Suche.

bisher lower_boundund upper_boundscheitern, 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 kann auch einen Algorithmus verwenden, der nicht zum Standard-Namespace gehört, solange er mit Containern kompatibel ist. Wie zum Beispiel boost::binary_search.

Robert Gould
quelle
2
In Bezug auf die Bearbeitung: Deshalb ist std :: same_range die Lösung. Andernfalls müssen Sie die Gleichheit testen (oder die Gleichwertigkeit, um mehr zu sein)
Luc Hermitte
Sie müssen die Gleichheit prüfen, nachdem Sie (unteres / oberes) _bound verwendet haben (siehe Antwort unten).
Luc Touraille
Die Dokumentation für die untere und obere Grenze besagt, dass der Bereich sortiert werden muss, und kann daher als binäre Suche implementiert werden.
Vividos
@vividos, Hurra! Sie haben genau die Dokumentation gefunden, über die ich Bescheid wissen musste! Vielen Dank!
Robert Gould
Robert, die Algorithmen Lower / Upper_bound / Equal_Range funktionieren nicht mit unsortierten Bereichen. Sie haben einfach Glück, dass sie mit dem Element arbeiten, das Sie genommen haben.
Luc Hermitte

Antworten:

97

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

Eine einfache Implementierung könnte sein

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 wäre die Verwendung von a std::set, die die Reihenfolge der Elemente garantiert und eine Methode bereitstellt iterator find(T key), die einen Iterator für das angegebene Element zurückgibt. Ihre Anforderungen sind jedoch möglicherweise nicht mit der Verwendung eines Satzes kompatibel (z. B. wenn Sie dasselbe Element mehrmals speichern müssen).

Luc Touraille
quelle
Ja, das funktioniert, und ich habe momentan eine ähnliche Implementierung, jedoch ist es eine "naive" Implementierung, in dem Sinne, dass der Kontext der Situation nicht genutzt wird, in diesem Fall sortierte Daten.
Robert Gould
5
Ich verstehe Ihren Kommentar nicht wirklich, da lower_bound nur für sortierte Daten verwendet werden kann. Die Komplexität ist geringer als bei der Verwendung von find (siehe Bearbeiten).
Luc Touraille
4
Um Lucs Antwort zu ergänzen, lesen Sie in Matt Austerns klassischem Artikel Warum Sie set nicht verwenden sollten und was Sie stattdessen verwenden sollten (C ++ Report 12: 4, April 2000), um zu verstehen, warum die binäre Suche mit sortierten Vektoren normalerweise std :: set vorzuziehen ist Dies ist ein baumbasierter assoziativer Container.
ZunTzu
16
Nicht benutzen *i == val! Eher benutzen !(val < *i). Der Grund dafür ist , dass die lower_boundAnwendungen <nicht ==(dh Tnicht einmal erforderlich Gleichheit vergleichbar sein). (Siehe Scott Meyers ' Effective STL für eine Erklärung des Unterschieds zwischen Gleichheit und Äquivalenz .)
gx_
1
@ CanKavaklıoğlu Es befindet sich kein Element bei end. Bereiche in der C ++ - Standardbibliothek werden mit halboffenen Intervallen dargestellt: Der Enditerator "zeigt" nach dem letzten Element. Als solches kann es von Algorithmen zurückgegeben werden, um anzuzeigen, dass kein Wert gefunden wurde.
Luc Touraille
9

Sie sollten einen Blick darauf werfen std::equal_range. Es werden zwei Iteratoren in den Bereich aller Ergebnisse zurückgesetzt.

Luc Hermitte
quelle
Laut cplusplus.com/reference/algorithm/equal_range sind die Kosten für std :: same_range ungefähr doppelt so hoch wie für std :: lower_bound. Es scheint, dass es einen Aufruf von std :: lower_bound und einen Aufruf von std :: upper_bound umschließt. Wenn Sie wissen, dass Ihre Daten keine Duplikate enthalten, ist dies ein Overkill, und std :: lower_bound (wie in der oberen Antwort gezeigt) ist die beste Wahl.
Bruce Dawson
@BruceDawson: cplusplus.com gibt nur eine Referenzimplementierung an, um das Verhalten anzugeben . Für eine tatsächliche Implementierung können Sie Ihre bevorzugte Standardbibliothek überprüfen. In llvm.org/svn/llvm-project/libcxx/trunk/include/algorithm können wir beispielsweise sehen, dass die Aufrufe von lower_bound und superior_bound in disjunkten Intervallen erfolgen (nach einer manuellen binären Suche). Davon abgesehen ist es wahrscheinlich teurer, insbesondere in Bereichen mit mehreren übereinstimmenden Werten.
Matthieu M.
6

Es gibt eine Reihe von ihnen:

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

Suchen nach:

Auf einem separaten Hinweis:

Sie dachten wahrscheinlich, dass die Suche nach Containern mehr als ein Ergebnis ergeben könnte. Aber gelegentlich, wenn Sie nur auf Existenz testen müssen, wäre auch eine optimierte Version schön.

Martin York
quelle
3
binary_search gibt keinen Iterator zurück, wie ich bereits erwähnt habe. Deshalb suche ich nach einer Alternative.
Robert Gould
1
Ja, ich weiß. Aber es passt in die Menge der binären Suchalgorithmen. Es ist also schön, dass andere davon erfahren.
Martin York
8
binary_search wird wie so viele andere Dinge in der STL einfach falsch benannt. Ich hasse, dass. Das Testen auf Existenz ist nicht dasselbe wie das Suchen nach etwas.
OregonGhost
2
Diese binären Suchfunktionen sind nicht hilfreich, wenn Sie den Index des gesuchten Elements kennen möchten. Ich muss meine eigene rekursive Funktion für diese Aufgabe schreiben. Ich hoffe, dass die Vorlage <Klasse T> int bindary_search (const T & item) zur nächsten Version von C ++ hinzugefügt werden sollte.
Kemin Zhou
3

Wenn std :: lower_bound für Ihren Geschmack zu niedrig ist, sollten Sie boost :: container :: flat_multiset überprüfen . Es ist ein Drop-In-Ersatz für std :: multiset, das mithilfe der binären Suche als sortierter Vektor implementiert wird.

ZunTzu
quelle
1
Gute Verbindung; und auch ein guter Link im Link: lafstern.org/matt/col1.pdf , der beschreibt, wie Lookups, die mit einem sortierten Vektor implementiert wurden, anstatt gesetzt zu werden (obwohl beide log (N) sind), signifikant bessere Proportionalitätskonstanten haben und ~ sind doppelt so schnell (der Nachteil ist eine größere INSERTION-Zeit).
Dan Nissenbaum
2

Die kürzeste Implementierung, die sich fragt, warum sie nicht in der Standardbibliothek enthalten ist:

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

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

trozen
quelle
Ich kann mir zwei Gründe vorstellen, warum dies nicht in der Standardbibliothek enthalten ist: Sie denken, dass es einfach zu implementieren ist, aber der Hauptgrund ist wahrscheinlich, dass möglicherweise eine umgekehrte Version von operator () () erforderlich ist, wenn der Wert nicht zuerst mit * austauschbar ist.
user877329
1

Überprüfen Sie diese Funktion, qBinaryFind :

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

Führt eine binäre Suche des Bereichs [Anfang, Ende] durch und gibt die Position eines Wertvorkommens zurück. Wenn kein Wert vorkommt, wird end zurückgegeben.

Die Elemente im Bereich [Anfang, Ende] müssen in aufsteigender Reihenfolge sortiert werden. siehe qSort ().

Wenn es viele Vorkommen mit demselben Wert gibt, kann eines davon zurückgegeben werden. Verwenden Sie qLowerBound () oder qUpperBound (), wenn Sie eine genauere Steuerung 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 ist im <QtAlgorithms>Header enthalten, der Teil der Qt- Bibliothek ist.

Gesetz und
quelle
1
Leider ist dieser Algorithmus nicht mit STL-Containern kompatibel.
Bartolo-Otrit
0

std :: lower_bound () :)

Moogs
quelle
OP: "Bisher scheitern Lower_bound und Upper_bound, weil ..."
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;
}

Beispiel: Betrachten Sie ein Array, A = [1,2,3,4,5,6,7,8,9] Angenommen, Sie möchten den Index 3 durchsuchen. Beginnen Sie zunächst mit 0 = 0 und beenden Sie jetzt mit 9-1 = 8 , da start <= end; Mitte = 4; (Array [Mitte], das 5 ist)! = 3 Nun liegt 3 links von Mitte, da es kleiner als 5 ist. Daher suchen wir nur den linken Teil des Arrays. Daher ist jetzt Start = 0 und Ende = 3; mid = 2.Since array [mid] == 3, daher haben wir die Nummer erhalten, nach der wir gesucht haben. Daher geben wir seinen Index zurück, der gleich mid ist.

Siddharth Kumar Shukla
quelle
1
Es ist gut, Code zu haben, aber Sie können die Antwort verbessern, indem Sie kurz erklären, wie dies für Personen funktioniert, die mit der Sprache noch nicht vertraut sind.
Taegost
Jemand hat Ihren Beitrag fälschlicherweise als minderwertig gekennzeichnet . Eine Nur- Code-Antwort ist nicht von geringer Qualität . Versucht es, die Frage zu beantworten? Wenn nicht, markieren Sie als "keine Antwort" oder empfehlen Sie das Löschen (falls in der Überprüfungswarteschlange). b) Ist es technisch falsch? Downvote oder Kommentar.
Wai Ha Lee
0

Eine Lösung, die die Position innerhalb des Bereichs zurückgibt, könnte wie folgt aussehen und nur Operationen für Iteratoren verwenden (dies sollte auch dann funktionieren, wenn der Iterator nicht rechnet):

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
quelle