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

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.

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).

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

Jest ich zestaw:

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

Szukaj:

• Dolna granica
• Górna granica
• equal_range
• binary_search

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.

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.

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

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 .

std :: lower_bound () :)

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.

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;

}