Gdzie mogę znaleźć „użyteczny” algorytm wyszukiwania binarnego w języku C ++?


106

Potrzebuję binarnego algorytmu wyszukiwania, który jest kompatybilny z kontenerami C ++ STL, coś std::binary_searchw rodzaju <algorithm>nagłówka biblioteki standardowej , ale potrzebuję go do zwrócenia iteratora wskazującego na wynik, a nie prostej wartości logicznej informującej mnie, czy element istnieje.

(Na marginesie, o czym myślała do cholery standardowa komisja, definiując API dla binary_search ?!)

Moim głównym zmartwieniem jest to, że potrzebuję szybkości wyszukiwania binarnego, więc chociaż mogę znaleźć dane za pomocą innych algorytmów, jak wspomniano poniżej, chcę wykorzystać fakt, że moje dane są sortowane, aby uzyskać korzyści z binarnego wyszukiwanie, a nie wyszukiwanie liniowe.

do tej pory lower_boundi upper_boundniepowodzenie, jeśli brakuje odniesienia:

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

Uwaga: mogę również używać algorytmu, który nie należy do przestrzeni nazw std, o ile jest zgodny z kontenerami. Powiedzmy boost::binary_search.


2
Odnośnie edycji: dlatego rozwiązaniem jest std :: equal_range. W przeciwnym razie będziesz musiał przetestować równość (lub równoważność, aby była większa)
Luc Hermitte

Musisz sprawdzić równość po użyciu (dolna / górna) _ograniczona (patrz odpowiedź poniżej).
Luc Touraille

Dokumentacja lower_bound i upper_bound stwierdza, że ​​zakres musi być posortowany, dzięki czemu można je zaimplementować jako wyszukiwanie binarne.
vividos

@vividos, hurra! znalazłeś tylko tę dokumentację, o której chciałem wiedzieć! Dzięki!
Robert Gould

Robert, algorytmy dolny / górny_graniczny / równy_zakres nie działają z nieposortowanymi zakresami. Masz szczęście, że widzisz, jak pracują z pobraną przez Ciebie próbką elementów.
Luc Hermitte

Odpowiedzi:


97

Nie ma takich funkcji, ale prostą można napisać za pomocą std::lower_bound, std::upper_boundlubstd::equal_range .

Może to być prosta implementacja

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
}

Innym rozwiązaniem byłoby użycie pliku std::set , który gwarantuje kolejność elementów i dostarcza metodę iterator find(T key)zwracającą iterator do danego elementu. Jednak Twoje wymagania mogą nie być zgodne z wykorzystaniem zestawu (na przykład, jeśli musisz wielokrotnie przechowywać ten sam element).


tak, to działa i mam teraz podobną implementację, jednak jest to implementacja „naiwna”, w tym sensie, że nie wykorzystuje kontekstu sytuacji, w tym przypadku posortowanych danych.
Robert Gould

5
Naprawdę nie rozumiem twojego komentarza, ponieważ lower_bound może być używane tylko w przypadku posortowanych danych. Złożoność jest mniejsza niż przy użyciu funkcji wyszukiwania (patrz edycja).
Luc Touraille

4
Aby uzupełnić odpowiedź Luca, zapoznaj się z klasycznym artykułem Matta Austern'a Why You Should Don't Use set, and What You Should Use Zamiast (Raport w C ++ 12: 4, kwiecień 2000), aby zrozumieć, dlaczego wyszukiwanie binarne z posortowanymi wektorami jest zwykle lepsze niż std :: set , który jest kontenerem asocjacyjnym opartym na drzewie.
ZunTzu

16
Nie używaj *i == val! Raczej używaj !(val < *i). Powodem jest to, że lower_boundużywa <, a nie ==(tj. TNie jest nawet wymagane, aby były porównywalne z równością). (Zobacz Efektywne STL Scotta Meyersa, aby uzyskać wyjaśnienie różnicy między równością a równoważnością ).
gx_

1
@ CanKavaklıoğlu Brak elementu znajdującego się w end. Zakresy w bibliotece standardowej C ++ są reprezentowane w półotwartych odstępach: iterator końcowy „wskazuje” po ostatnim elemencie. W związku z tym może zostać zwrócony przez algorytmy, aby wskazać, że nie znaleziono żadnej wartości.
Luc Touraille

9

Powinieneś rzucić okiem std::equal_range. Zwróci parę iteratorów do zakresu wszystkich wyników.


Według cplusplus.com/reference/algorithm/equal_range koszt std :: equal_range jest około dwa razy wyższy niż std :: lower_bound. Wygląda na to, że zawija wywołanie std :: lower_bound i wywołanie std :: upper_bound. Jeśli wiesz, że twoje dane nie mają duplikatów, to jest to przesada, a std :: lower_bound (jak pokazano w górnej odpowiedzi) jest najlepszym wyborem.
Bruce Dawson

@BruceDawson: cplusplus.com podaje tylko implementację referencyjną do określenia zachowania ; dla rzeczywistej implementacji możesz sprawdzić swoją ulubioną bibliotekę standardową. Na przykład na llvm.org/svn/llvm-project/libcxx/trunk/include/algorithm możemy zobaczyć, że wywołania bottom_bound i upper_bound są wykonywane w rozłącznych odstępach czasu (po pewnym ręcznym wyszukiwaniu binarnym). Mimo to prawdopodobnie będzie droższy, zwłaszcza w zakresach z wieloma dopasowanymi wartościami.
Matthieu M.

6

Jest ich zestaw:

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

Szukaj:

W osobnej notatce:

Prawdopodobnie myśleli, że wyszukiwanie kontenerów może dać więcej niż jeden wynik. Ale w dziwnych przypadkach, gdy wystarczy przetestować istnienie zoptymalizowanej wersji, również byłaby miła.


3
binary_search nie zwraca iteratora, jak wspomniałem wcześniej, dlatego szukam alternatywy.
Robert Gould

1
Tak, wiem. Ale pasuje do zestawu algorytmów wyszukiwania binarnego. Więc miło, że inni wiedzą o tym.
Martin York

8
binary_search jest po prostu, podobnie jak wiele innych rzeczy w STL, nazwany nieprawidłowo. Nienawidzę tego. Testowanie istnienia to nie to samo, co szukanie czegoś.
OregonGhost

2
Te funkcje wyszukiwania binarnego nie są przydatne w przypadku, gdy chcesz poznać indeks elementu, którego szukasz. Muszę napisać własną funkcję rekurencyjną dla tego zadania. Mam nadzieję, że ten szablon <class T> int bindary_search (const T & item) powinien zostać dodany do następnej wersji C ++.
Kemin Zhou

3

Jeśli std :: lower_bound jest zbyt niski dla twoich upodobań, możesz sprawdzić boost :: container :: flat_multiset . Jest to zamiennik typu drop-in dla std :: multiset zaimplementowany jako posortowany wektor przy użyciu wyszukiwania binarnego.


1
Dobry link; a także dobry link w linku: lafstern.org/matt/col1.pdf , który opisuje, w jaki sposób wyszukiwania zaimplementowane z posortowanym wektorem zamiast zestawu (chociaż oba są log (N)), mają znacznie lepsze stałe proporcjonalności i są ~ dwa razy szybciej (wadą jest dłuższy czas WSTAWIANIA).
Dan Nissenbaum,

2

Najkrótsza implementacja, zastanawiasz się, dlaczego nie ma jej w standardowej bibliotece:

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

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


Przychodzą mi do głowy dwa powody, dla których nie ma tego w bibliotece standardowej: uważają, że jest łatwe do zaimplementowania, ale głównym powodem jest prawdopodobnie to, że może wymagać odwróconej wersji operatora () (), jeśli wartość nie jest wymienna z * first.
user877329

1

Sprawdź tę funkcję, qBinaryFind :

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

Wykonuje binarne wyszukiwanie zakresu [początek, koniec) i zwraca pozycję wystąpienia wartości. Jeśli nie ma wystąpień value, zwraca koniec.

Elementy w zakresie [początek, koniec) muszą być posortowane w kolejności rosnącej; zobacz qSort ().

Jeśli istnieje wiele wystąpień o tej samej wartości, można zwrócić dowolne z nich. Użyj qLowerBound () lub qUpperBound (), jeśli potrzebujesz dokładniejszej kontroli.

Przykład:

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)

Funkcja jest zawarta w <QtAlgorithms>nagłówku, który jest częścią biblioteki Qt .


1
Niestety ten algorytm nie jest kompatybilny z kontenerami STL.
bartolo-otrit


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

Przykład: Rozważ tablicę, A = [1,2,3,4,5,6,7,8,9] Załóżmy, że chcesz przeszukać indeks 3 Początkowo, start = 0 i end = 9-1 = 8 Teraz , od początku <= koniec; mid = 4; (tablica [mid], która wynosi 5)! = 3 Teraz 3 leży na lewo od środka, ponieważ jest mniejsze niż 5. Dlatego przeszukujemy tylko lewą część tablicy. Stąd start = 0 i end = 3; mid = 2. Ponieważ array [mid] == 3, otrzymaliśmy liczbę, której szukaliśmy. Dlatego zwracamy jego indeks równy połowie.


1
Dobrze jest mieć kod, ale możesz poprawić odpowiedź, podając krótkie wyjaśnienie, jak to działa dla osób, które są nowicjuszami w tym języku.
Taegost,

Ktoś nieprawidłowo oznaczył Twój post jako niskiej jakości . Odpowiedź zawierająca tylko kod nie jest niskiej jakości . Czy próbuje odpowiedzieć na pytanie? Jeśli nie, oznacz jako „nie jest odpowiedzią” lub zalecaj usunięcie (jeśli znajduje się w kolejce do sprawdzenia). b) Czy jest to niepoprawne technicznie? Głosuj przeciw lub komentuj.
Wai Ha Lee,

0

Rozwiązanie zwracające pozycję wewnątrz zakresu mogłoby wyglądać następująco, używając tylko operacji na iteratorach (powinno działać nawet jeśli iterator nie wykonuje arytmetyki):

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;

}
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.