W pierwszej części artykułu przedstawiona została biblioteczna funkcja std::bsearch (plik nagłówkowy cstdlib) realizująca algorytm wyszukiwania binarnego. Jej korzenie sięgają biblioteki standardowej języka C. Ma to swoje konsekwencje w postaci relatywnie skomplikowanego interfejsu oferowanego przez tą funkcję (aż 5 parametrów oraz często pojawiający się typ void * lub const void * wymagający częstych rzutowań). Ponadto zastosowano funkcję sortującą o podobnym interfejsie do funkcji std::bsearch czyli std::qsort (plik nagłówkowy cstdlib), ponieważ algorytm wyszukiwania binarnego wymaga uprzedniego posortowania przeszukiwanej kolekcji danych. Warto w tym miejscu zaznaczyć, iż funkcja std::bsearch zwraca wskaźnik (void *) do odnalezionego elementu kolekcji danych (lub wskaźnik NULL w przypadku braku takiego elementu w kolekcji). Otrzymany w ten sposób wskaźnik możemy wykorzystać m.in. do modyfikacji odnalezionego elementu lub wyznaczenia jego względnego położenia (indeksu) w przeszukiwanej kolekcji danych.
W drugiej części artykułu przedstawiona zostanie funkcja (algorytm) std::binary_search (plik nagłówkowy algorithm), należąca do biblioteki standardowej języka C++. Interfejs tej funkcji jest dużo bardziej przyjazny dla użytkownika w porównaniu do interfejsu jaki oferuje funkcja std::bsearch. Wynika to przede wszystkim z faktu, iż funkcja std::binary_search została zaimplementowana w sposób prawdziwie generyczny. Jest to bowiem szablon funkcji, który podczas wykonywania algorytmu wyszukiwania binarnego odwołuje się do elementów kolekcji danych za pośrednictwem iteratorów. Jeżeli przeszukiwana kolekcja danych jest posortowana rosnąco oraz odpowiada nam działanie relacyjnego operatora < zdefiniowanego dla naszego typu danych, wówczas możemy zrezygnować z dostarczania komparatora (jest to odpowiednik funkcji porównującej dostarczanej do funkcji std::bsearch za pośrednictwem wskaźnika do funkcji). W przypadku funkcji std::bsearch dostarczenie funkcji porównującej jest obligatoryjne. Jeżeli dane posortowane są w sposób malejący nadal nie musimy implementować komparatora, bowiem z pomocą przychodzi nam biblioteczna struktura std::greater (plik nagłówkowy functional) umożliwiająca przekazanie właściwego obiektu komparatora. Domyślne zachowanie (funkcja std::binary_search bez komparatora) dla kolekcji danych posortowanych rosnąco jest równoważne użyciu komparatora typu std::less (plik nagłówkowy functional). Może się jednak okazać, iż specyfika typu danych przechowywanych w kolekcji wymaga samodzielnie napisanego komparatora. W porównaniu do funkcji std::bsearch nie jesteśmy jednak ograniczeni wyłącznie do funkcji (przekazywanej przez wskaźnik do funkcji). W przypadku funkcji std::binary search możemy bowiem dostarczyć odpowiedni obiekt funkcyjny, którego typem może być samodzielnie zaimplementowana struktura oferująca odpowiedni predykat, przy czym na ogół najwygodniejszym podejściem będzie tutaj zastosowanie wyrażenia lambda (ang. lambda expression). Jak się wkrótce okaże, pomimo oczywistych zalet w zakresie użytkowania funkcji std::binary_search (w porównaniu do funkcji std::bsearch) jej interfejs nie zawsze musi nam odpowiadać. Na szczęście własna implementacja tej funkcji jest stosunkowo łatwa bowiem można ją oprzeć na bibliotecznych funkcjach (algorytmach) takich jak (plik nagłówkowy algorithm) :
Przykładowe implementacje zostaną przedstawione w dalszej części tego artykułu.
Funkcja (algorytm) std::binary_search
Interfejs funkcji std::binary_search dostępny jest w dwóch wersjach :
template<class ForwardIt, class T> bool binary_search(ForwardIt first, ForwardIt last, const T& value);
template<class ForwardIt, class T, class Compare> bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp);
Jest to szablon funkcji parametryzowany typem iteratora początkowego/końcowego (ForwardIt), typu poszukiwanej wartości (T) oraz w przypadku drugiej wersji dodatkowo typem komparatora (Compare). Typy te mają swoje bezpośrednie odzwierciedlenie w typach parametrów funkcji std::binary_search:
- first – iterator wskazujący na początek przeszukiwanej kolekcji danych
- last – iterator wskazujący na koniec (następny po ostatnim elemencie wskazanej kolekcji danych) przeszukiwanej kolekcji danych
- value – referencja do stałej zawierającej poszukiwaną wartość
- comp – komparator (funkcja, obiekt funkcyjny lub wyrażenie lambda) odwołujący się najczęściej do operatorów relacyjnych
Jak więc widać interfejs funkcji std::binary_search już na pierwszy rzut oka jest łatwy w zrozumieniu (czego nie można powiedzieć o interfejsie funkcji std::bsearch). Funkcja ta ma w zależności od wariantu 3 lub 4 parametry z czego pierwsze dwa dotyczą iteratorów wyznaczających zakres przeszukiwanych danych (dla porównania funkcja std::bsearch ma tych parametrów aż 5). Dzięki generycznej implementacji zniknęły również wszechobecne w funkcji std::bsearch parametry typu void * oraz const void *. Nie potrzebujemy ponadto informacji dotyczącej rozmiaru całej kolekcji danych jak i jej pojedynczego elementu.
Dodatkowego komentarza wymaga jedynie typ iteratora. Parametryczna nazwa tego typu ForwardIt informuje nas, że musimy dostarczyć iterator o właściwościach przynajmniej takich jakie oferuje jednokierunkowy iterator postępujący (ang. forward iterator), który musi implementować m.in. operatory ++ (operatotry preinkrementacji oraz postinkrementacji) oraz operator * (operator ”wyłuskania”). W praktyce oznacza to, iż za pomocą funkcji std::binary_search możemy przeszukiwać różne struktury danych zaczynając od listy jednokierunkowej std::forward_list (plik nagłówkowy forward_list), poprzez listę dwukierunkową std::list (plik nagłówkowy list), a kończąc na kontenerach z dostępem swobodnym takich jak std::vector (plik nagłówkowy vector)
Część praktyczną rozpoczniemy od przykładu przedstawiającego użycie pierwszej wersji funkcji std::binary_search (bez komparatora) dla danych typu int (przechowywanych w kontenerze std::vector):
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
int main()
{
std::vector<int> data = { 3, 7, 5, 8, 7, 2, 9, 4, 1, 7, 6, 0 };
std::sort(std::begin(data), std::end(data));
copy(std::begin(data), std::end(data),
std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
int val = 7;
bool found = std::binary_search(std::begin(data), std::end(data), val);
std::cout << val << " " << (found ? "found" : "not found") << '\n';
}
0 1 2 3 4 5 6 7 7 7 8 9 7 found
W przypadku nie znalezienia szukanego elementu również otrzymamy spodziewany output:
0 1 2 3 4 5 6 7 7 7 8 9 10 not found
Powyższy kod źródłowy oparty jest na generycznych funkcjach std::binary_search oraz std::sort (plik nagłówkowy algorithm). Oznacza to, iż zmiana typu z int na std::string (plik nagłówkowy string) praktycznie nie zmieni naszego kodu źródłowego (nie licząc danych wejściowych oraz wzorcowego elementu do porównania), bowiem polegamy tutaj na relacyjnym operatorze < zaimplementowanym dla typu std::string:
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
int main()
{
std::vector<std::string> data = {
"January",
"February",
"March",
"April",
"May",
"June",
"July",
"August",
"September",
"October",
"November",
"December"
};
std::sort(std::begin(data), std::end(data));
copy(std::begin(data), std::end(data),
std::ostream_iterator<std::string>(std::cout, "\n"));
std::cout << '\n';
std::string val = "July";
bool found = std::binary_search(std::begin(data), std::end(data), val);
std::cout << val << " " << (found ? "found" : "not found") << '\n';
}
April August December February January July June March May November October September July found
April August December February January July June March May November October September Lipiec not found
Przejdźmy teraz do drugiej wersji funkcji std::binary_search, której dodatkowym parametrem jest komparator. Komparator może być potrzebny przede wszystkim w dwóch podstawowych przypadkach:
- dane posortowane są w porządku malejącym (pierwsza wersja funkcji std::binary_search zakłada, że dane posortowane są w porządku rosnącym)
- operatory relacyjne dla przechowywanego typu danych nie są odpowiednie w konkretnej sytuacji (pierwsza wersja funkcji std::binary_search wykorzystuje relacyjny operator < zdefiniowany dla określonego typu danych znajdujących się w przeszukiwanej kolekcji)
Zacznijmy od pierwszego przypadku, w którym nasze dane (przyjmiemy, że są one typu int) posortowane są porządku malejącym. W tym celu jako komparator podamy obiekt funkcyjny, którego typem jest std::greater:
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
int main()
{
std::vector<int> data = { 3, 7, 5, 8, 7, 2, 9, 4, 1, 7, 6, 0 };
std::sort(std::begin(data), std::end(data), std::greater<int>());
copy(std::begin(data), std::end(data),
std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
int val = 7;
bool found = std::binary_search(std::begin(data), std::end(data), val,
std::greater<int>());
std::cout << val << " " << (found ? "found" : "not found") << '\n';
}
9 8 7 7 7 6 5 4 3 2 1 0 7 found
9 8 7 7 7 6 5 4 3 2 1 0 10 not found
Na uwagę zasługuje fakt, iż zarówno do funkcji std::binary_search oraz funkcji std::sort (algorytm sortowania będący odpowiednikiem funkcji std::qsort), przekazujemy obiekt funkcyjny tego samego typu (std::greater). Jest to podejście analogiczne do tego zastosowanego dla pary funkcji std::bsearch oraz std::qsort, którym przekazano wskaźnik do tej samej funkcji porównującej. Oczywiście domyślny przypadek (pierwsza wersja funkcji std::binary_search) będzie równoważny z użyciem komparatora std::less:
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
int main()
{
std::vector<int> data = { 3, 7, 5, 8, 7, 2, 9, 4, 1, 7, 6, 0 };
std::sort(std::begin(data), std::end(data), std::less<int>());
copy(std::begin(data), std::end(data),
std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
int val = 7;
bool found = std::binary_search(std::begin(data), std::end(data), val,
std::less<int>());
std::cout << val << " " << (found ? "found" : "not found") << '\n';
}
0 1 2 3 4 5 6 7 7 7 8 9 7 found
0 1 2 3 4 5 6 7 7 7 8 9 10 not found
W standardzie C++14 pojawiły się transparentne wersje szablonów struktur takich jak std::less czy std::greater. W skrócie, są to szablony struktur, dla których zaimplementowano ich specjalizację dla typu void. Specyfika tej specjalizacji polega na tym, że operator () jest szablonem funkcji, co pozwala kompilatorowi wygenerować odpowiedni obiekt funkcyjny, bez konieczności jawnego podawania typu poszukiwanej danej (podczas konkretyzacji szablonu struktury). W poniższym przykładzie zauważ, iż zamiast ”std::greater<int>()” napisałem ”std::greater<>()”:
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
int main()
{
std::vector<int> data = { 3, 7, 5, 8, 7, 2, 9, 4, 1, 7, 6, 0 };
std::sort(std::begin(data), std::end(data), std::greater<>());
copy(std::begin(data), std::end(data),
std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
int val = 7;
bool found = std::binary_search(std::begin(data), std::end(data), val,
std::greater<>());
std::cout << val << " " << (found ? "found" : "not found") << '\n';
}
9 8 7 7 7 6 5 4 3 2 1 0 7 found
9 8 7 7 7 6 5 4 3 2 1 0 10 not found
W drugim przypadku mamy do czynienia z typem danych dla którego operatory relacyjne nie spełniają swojego zadania. Przykładem takiego typu jest oczywiście const char *, bowiem nie zależy nam na wartości wskaźnika, lecz na treści która znajduje się pod adresem pamięci przechowywanym przez ten wskaźnik. Tym razem będziemy musieli utworzyć swój własny komparator i w tym celu posłużymy się wyrażeniem lambda (przyjmujemy sortowanie w porządku rosnącym):
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
int main()
{
// Lambda expression
auto comp = [](const char *lhs, const char *rhs)
{
std::string l = lhs;
std::string r = rhs;
return l < r;
};
std::vector<const char *> data = {
"January",
"February",
"March",
"April",
"May",
"June",
"July",
"August",
"September",
"October",
"November",
"December"
};
std::sort(std::begin(data), std::end(data), comp);
copy(std::begin(data), std::end(data),
std::ostream_iterator<std::string>(std::cout, "\n"));
std::cout << '\n';
const char *val = "July";
bool found = std::binary_search(std::begin(data), std::end(data), val, comp);
std::cout << val << " " << (found ? "found" : "not found") << '\n';
}
April August December February January July June March May November October September July found
April August December February January July June March May November October September Lipiec not found
Być może zaskakujący jest fakt, iż funkcja std::binary_search zamiast iteratora wskazującego znaleziony element, zwraca wartość typu bool, co oznacza, iż otrzymujemy jedynie zero-jedynkową informację o istnieniu poszukiwanej wartości. Nie możemy więc w tak jak w przypadku funkcji std::bsearch odwoływać się do odnalezionej wartości. Typowe implementacje funkcji std::binary_search mają postać:
template<class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value)
{
first = std::lower_bound(first, last, value);
return (!(first == last) && !(value < *first));
}
template<class ForwardIt, class T, class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
first = std::lower_bound(first, last, value, comp);
return (!(first == last) && !(comp(value, *first)));
}
Okazuje się więc, że funkcja std::binary_search to w zasadzie opakowanie funkcji std::lower_bound, który zwraca iterator do pierwszego elementu którego wartość jest większa lub równa poszukiwanej wartości. Oto interfejs tej funkcji (również w dwóch odpowiadających wersjach):
template< class ForwardIt, class T > ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
template<class ForwardIt, class T, class Compare> ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp);
Interfejs ten jest prawie takim sam jak w przypadku funkcji std::binary_search. Jedyna różnica polega na typie zwracanym. W przypadku funkcji std::lower_bound jest to iterator do odnalezionego elementu, czyli to na czym nam zależy. Wykorzystamy ten fakt do implementacji własnej wersji funkcji std::binary_search, która zostanie przedstawiona w dalszej części artykułu.
Funkcja (algorytm) std::sort
Funkcję std::binary_search używamy wraz z funkcją (algorytmem) std::sort. Jest to więc analogiczna sytuacja jak dla pary funkcji std::bsearch oraz std::qsort. Funkcje std::bsearch oraz std::qsort mają także podobne interfejsy. W przypadku funkcji std::binary_search oraz std::sort analogia ta nie jest w pełni zachowana:
template<class ForwardIt, class T> bool binary_search(ForwardIt first, ForwardIt last, const T& value);
template<class RandomIt> void sort(RandomIt first, RandomIt last);
Wersja z komparatorem:
template<class ForwardIt, class T, class Compare> bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp);
template< class RandomIt, class Compare > void sort(RandomIt first, RandomIt last, Compare comp);
Problem stanowi tutaj możliwy typ iteratora. Jak już wcześniej wspomniałem funkcja std::binary_search obsługuje struktury danych, dla których iterator spełnia przynjamniej wymagania stawiane iteratorom postępującym. Inaczej jest w przypadku funkcji std::sort, wymagającej iteratora o dostępie swobodnym (ang. random access iterator) – stąd nazwa parametryczna typu – RandomIt (iterator taki wymaga zdefiniowania dodatkowych operatorów, w tym operatora tablicowego [ ]). W praktyce oznacza to, iż w takim przypadku nie możemy korzystać z kontenera typu std::list, który obsługiwany jest przez ”uboższy” iterator dwukierunkowy (ang. bidirectional iterator). Ewentualna próba kompilacji takiego kodu źródłowego zakończy się błędem. Prawidłowe rozwiązanie wymaga wywołania metody sort, która jest składową klasy std::list:
#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>
int main()
{
std::list<int> data = { 3, 7, 5, 8, 7, 2, 9, 4, 1, 7, 6, 0 };
data.sort();
copy(std::begin(data), std::end(data),
std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
int val = 7;
bool found = std::binary_search(std::begin(data), std::end(data), val);
std::cout << val << " " << (found ? "found" : "not found") << '\n';
}
0 1 2 3 4 5 6 7 7 7 8 9 7 found
0 1 2 3 4 5 6 7 7 7 8 9 10 not found
Wersja z komparatorem:
#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>
int main()
{
std::list<int> data = { 3, 7, 5, 8, 7, 2, 9, 4, 1, 7, 6, 0 };
data.sort(std::greater<int>());
copy(std::begin(data), std::end(data), std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
int val = 7;
bool found = std::binary_search(std::begin(data), std::end(data), val, std::greater<int>());
std::cout << val << " " << (found ? "found" : "not found") << '\n';
}
9 8 7 7 7 6 5 4 3 2 1 0 7 found
9 8 7 7 7 6 5 4 3 2 1 0 10 not found
Implementacja 1 (std::lower_bound)
template<class ForwardIt, class T>
ForwardIt binary_search(ForwardIt first, ForwardIt last, const T & value)
{
auto low = std::lower_bound(first, last, value);
if ((low != last) && !(value < *low))
return low;
return last;
}
template<class ForwardIt, class T, class Comp>
ForwardIt binary_search(ForwardIt first, ForwardIt last, const T & value, Comp comp)
{
auto low = std::lower_bound(first, last, value, comp);
if ((low != last) && !comp(value, *low))
return low;
return last;
}
Rozwiązanie ta bazuje na typowej impementacji funkcji std::binary_search przedstawionej w tym artykule. Jej zasadniczym składnikiem jest algorytm std::lower_bound, który zwraca iterator do pierwszewgo elementu o wartości większej lub równej poszukiwanej wartości (w przypadku nie znalezienia elementu spełniającego ten warunek, zwracany jest iterator końcowy). Mamy tutaj dwa warunki (muszą być spełnione jednocześnie) określające czy poszukiwana wartość została znaleziona:
- Iterator zwrócony przez funkcję std::lower_bound wskazuje na element o wartości większej lub równej poszukiwanej wartości (jest to warunek konieczny ale nie wystarczający) – w przeciwnym wypadku otrzymamy iterator końcowy
- Iterator zwrócony przez funkcję std::lower_bound wskazuje na element o wartości nie większej od poszukiwanej wartości (warunek ten może być spełniony jeśli pierwszy z nich jest spełniony)
Jeżeli oba z powyższych warunków nie zostaną spełnione, wówczas nasza funkcja binary_search zwraca iterator końcowy oznaczający brak poszukiwanej wartości w przeszukiwanej kolekcji danych. Poniżej przedstawiam przykład użycia naszej implementacji:
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
namespace nonstd
{
template<class ForwardIt, class T>
ForwardIt binary_search(ForwardIt first, ForwardIt last, const T & value)
{
auto low = std::lower_bound(first, last, value);
if ((low != last) && !(value < *low))
return low;
return last;
}
}
int main()
{
std::vector<int> data = { 3, 7, 5, 8, 7, 2, 9, 4, 1, 7, 6, 0 };
std::sort(std::begin(data), std::end(data));
copy(std::begin(data), std::end(data),
std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
int val = 7;
auto ans = nonstd::binary_search(std::begin(data), std::end(data), val);
if (ans != std::end(data))
std::cout << *ans << " found at index "
<< std::distance(std::begin(data), ans) << '\n';
else
std::cout << val << " not found\n";
}
0 1 2 3 4 5 6 7 7 7 8 9 7 found at index 7
0 1 2 3 4 5 6 7 7 7 8 9 10 not found
Wersja z komparatorem:
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
namespace nonstd
{
template<class ForwardIt, class T, class Comp>
ForwardIt binary_search(ForwardIt first, ForwardIt last, const T & value,
Comp comp)
{
auto low = std::lower_bound(first, last, value, comp);
if ((low != last) && !comp(value, *low))
return low;
return last;
}
}
int main()
{
std::vector<int> data = { 3, 7, 5, 8, 7, 2, 9, 4, 1, 7, 6, 0 };
std::sort(std::begin(data), std::end(data), std::greater<int>());
copy(std::begin(data), std::end(data),
std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
int val = 7;
auto ans = nonstd::binary_search(std::begin(data), std::end(data), val,
std::greater<int>());
if (ans != std::end(data))
std::cout << *ans << " found at index "
<< std::distance(std::begin(data), ans) << '\n';
else
std::cout << val << " not found\n";
}
9 8 7 7 7 6 5 4 3 2 1 0 7 found at index 2
9 8 7 7 7 6 5 4 3 2 1 0 10 not found
Implementacja 2 (std::lower_bound + std::upper+bound)
template<class ForwardIt, class T>
ForwardIt binary_search(ForwardIt first, ForwardIt last, const T & value)
{
auto low = std::lower_bound(first, last, value);
auto up = std::upper_bound(first, last, value);
if (low != up)
return low;
return last;
}
template<class ForwardIt, class T, class Comp>
ForwardIt binary_search(ForwardIt first, ForwardIt last, const T & value, Comp comp)
{
auto low = std::lower_bound(first, last, value, comp);
auto up = std::upper_bound(first, last, value, comp);
if (low != up)
return low;
return last;
}
W implementacji tej występuje tylko jeden warunek istnienia elementu o poszukiwanej wartości. Jest to możlwe dziękie zastsowaniu pary algorytmów std::lower_bound i std::upper_bound. Funkcja std::upper_bound zwraca iterator do pierwszewgo elementu, którego wartość jest większa od poszukiwanej wartości (w przypadku nie znalezienia elementu spełniającego ten warunek, zwracany jest iterator końcowy). W prównaniu do funkcji std::lower_bound, funkcja std::upper_bound nie bierze pod uwagę elementu o wartości równej poszukiwanej wartości. Obserwacja to pozwala nam zdefiniować prosty warunek znalezienia poszukiwanej wartości. Warunek ten będzię spełniony jeśli obie wspomniane funkcje zwrócą iteratory do różnych wartości. W przeciwnym wypadku nasza funkcja binary_search zwaraca iterator końcowy. W szczególnym przypadku, jeżeli w kolekcji danych nie istnieje element o wartości większej lub równej poszukiwanej wartości, wówczas obie funkcje zwrócą ten sam iterator końcowy i warunek znalezienia poszukiwanej wartości nie zostanie spełniony. Poniżej przedstawiam przykład użycia naszej implementacji:
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
namespace nonstd
{
template<class ForwardIt, class T>
ForwardIt binary_search(ForwardIt first, ForwardIt last, const T & value)
{
auto low = std::lower_bound(first, last, value);
auto up = std::upper_bound(first, last, value);
if (low != up)
return low;
return last;
}
}
int main()
{
std::vector<int> data = { 3, 7, 5, 8, 7, 2, 9, 4, 1, 7, 6, 0 };
std::sort(std::begin(data), std::end(data));
copy(std::begin(data), std::end(data),
std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
int val = 10;
auto ans = nonstd::binary_search(std::begin(data), std::end(data), val);
if (ans != std::end(data))
std::cout << *ans << " found at index "
<< std::distance(std::begin(data), ans) << '\n';
else
std::cout << val << " not found\n";
}
0 1 2 3 4 5 6 7 7 7 8 9 7 found at index 7
0 1 2 3 4 5 6 7 7 7 8 9 10 not found
Wersja z komparatorem:
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
namespace nonstd
{
template<class ForwardIt, class T, class Comp>
ForwardIt binary_search(ForwardIt first, ForwardIt last, const T & value,
Comp comp)
{
auto low = std::lower_bound(first, last, value, comp);
auto up = std::upper_bound(first, last, value, comp);
if (low != up)
return low;
return last;
}
}
int main()
{
std::vector<int> data = { 3, 7, 5, 8, 7, 2, 9, 4, 1, 7, 6, 0 };
std::sort(std::begin(data), std::end(data), std::greater<int>());
copy(std::begin(data), std::end(data),
std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
int val = 7;
auto ans = nonstd::binary_search(std::begin(data), std::end(data), val,
std::greater<int>());
if (ans != std::end(data))
std::cout << *ans << " found at index "
<< std::distance(std::begin(data), ans) << '\n';
else
std::cout << val << " not found\n";
}
9 8 7 7 7 6 5 4 3 2 1 0 7 found at index 2
9 8 7 7 7 6 5 4 3 2 1 0 10 not found
Implementacja 3 (std::equal_range)
template<class ForwardIt, class T>
ForwardIt binary_search(ForwardIt first, ForwardIt last, const T & value)
{
auto [low, up] = std::equal_range(first, last, value);
if (low != up)
return low;
return last;
}
template<class ForwardIt, class T, class Comp>
ForwardIt binary_search(ForwardIt first, ForwardIt last, const T & value, Comp comp)
{
auto [low, up] = std::equal_range(first, last, value, comp);
if (low != up)
return low;
return last;
}
Jest to moim zdaniem najbardziej elegancka z przedstawionych tutaj implementacji. Działa ona tak samo jak poprzednia implementacja oparta na parze funkcji std::lower_bound i std::upper_bound, a to za sprawą użytej tutaj funkcji std::equal_range:
template<class ForwardIt, class T>
std::pair<ForwardIt,ForwardIt>
equal_range(ForwardIt first, ForwardIt last, const T & value)
{
return std::make_pair(std::lower_bound(first, last, value),
std::upper_bound(first, last, value));
}
template<class ForwardIt, class T, class Compare>
std::pair<ForwardIt,ForwardIt>
equal_range(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
return std::make_pair(std::lower_bound(first, last, value, comp),
std::upper_bound(first, last, value, comp));
}
Funkcja ta zwraca parę iteratów pochodzących z wyżej wymienionych funkcji std::lower_bound i std::upper_bound. Implementacja ta została napisana zgodnie ze standardem C++17, bowiem użyłem tutaj deklaracji strukturalnego wiązania (ang. structured binding declaration). Poniżej przedstawiam przykład użycia naszej implementacji:
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
namespace nonstd
{
template<class ForwardIt, class T>
ForwardIt binary_search(ForwardIt first, ForwardIt last, const T & value)
{
auto [low, up] = std::equal_range(first, last, value);
if (low != up)
return low;
return last;
}
}
int main()
{
std::vector<int> data = { 3, 7, 5, 8, 7, 2, 9, 4, 1, 7, 6, 0 };
std::sort(std::begin(data), std::end(data));
copy(std::begin(data), std::end(data),
std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
int val = 7;
auto ans = nonstd::binary_search(std::begin(data), std::end(data), val);
if (ans != std::end(data))
std::cout << *ans << " found at index "
<< std::distance(std::begin(data), ans) << '\n';
else
std::cout << val << " not found\n";
}
0 1 2 3 4 5 6 7 7 7 8 9 7 found at index 7
0 1 2 3 4 5 6 7 7 7 8 9 10 not found
Wersja z komparatorem:
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
namespace nonstd
{
template<class ForwardIt, class T, class Comp>
ForwardIt binary_search(ForwardIt first, ForwardIt last, const T & value,
Comp comp)
{
auto [low, up] = std::equal_range(first, last, value, comp);
if (low != up)
return low;
return last;
}
}
int main()
{
std::vector<int> data = { 3, 7, 5, 8, 7, 2, 9, 4, 1, 7, 6, 0 };
std::sort(std::begin(data), std::end(data), std::greater<int>());
copy(std::begin(data), std::end(data),
std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
int val = 7;
auto ans = nonstd::binary_search(std::begin(data), std::end(data), val,
std::greater<int>());
if (ans != std::end(data))
std::cout << *ans << " found at index "
<< std::distance(std::begin(data), ans) << '\n';
else
std::cout << val << " not found\n";
}
9 8 7 7 7 6 5 4 3 2 1 0 7 found at index 2
9 8 7 7 7 6 5 4 3 2 1 0 10 not found
Wspólnym mianownikiem przedstawionych implementacji jest funkcja std::lower_bound (wywoływana pośrednio lub bezpośrednio). Ma to swoje konsekwencje w przypadku znalezienia poszukiwanej wartości wśród powtarzających się elemetów kolekcji danych. Dzięki zastosowaniu funkcji std::lower_bound mamy gwarancję, iż w przypadku znalezienia poszukiwanej wartości, otrzymamy iterator do pierwszego wystąpienia powtarzającego się elementu (jak już wiemy, funkcja std::bsearch nie daje takiej gwarancji).
Podsumowanie
- Funkcja std::binary_search został zaimplemtowany w sposób generyczny, przez co jego interfejs jest bardziej przyjazny dla użytkownika w porównaniu do funkcji std::bsearch
- Funkcja std::binary_search występuj w dwóch wariantach: z komparatorem (jest on dodatkowym parametrem obok pary iteratorów wyznaczającyh zakres przeszukiwanych danych oraz referencji do stałej zawierającej poszukiwaną wartość) oraz bez komparatora (wykorzystuje operator < zdefiniowany dla typu przeszukiwanych danych, zakładając że dane posortowane są w porządku rosnącym)
- Funkcja std::binary_search wymaga pary iteratorów spełniających wymagania stawiane przynjamniej dla iteratrów postępujących
- Sortowanie danych możemy wykonać z pomocą funkcji std::sort, przy czym należy mieć na uwadze, iż wymaga on iteratorów o dostępie swobodnym (w przypadku kontenerów takich jak std::list należy korzystać z metody składowej sort)
- Użycie komparatora jest niezbędne m.in. w przypadku gdy dane posortowane są w porządku malejącym oraz gdy operatory relacyjne zdefiniowane dla typu przeszukiwanych danych nie są odpowiednie w konkretnej sytuacji (przykładem może tu być typ const char *)
- Isnieje możliwośc skorzystania z gotowych komparatorów (szablonów struktur) takich jak: std::less czy std::greater (standard C++14 umożliwia korzystanie z transparentnych wersji tych struktur)
- Implementacja funkcji std::binary_search oparta jest na funkcji std::lower_bound, która zwraca iterator do pierwszego elementu, którego wartość jest większa lub równa poszukiwanej wartości
- Funkcja std::binary_search zwraca typ bool co nie zawsze musi nam odpowiadać – włąsną wersję tej funkcji, zwracającą iterator do elementu zawierającego poszukiwaną wartością, można łatwo zaimplementować z wykorzystaniem takich funkcji jak: std::lower_bound, std::upper_bound, czy std::equal_range
- Zastosowanie funkcji std::lower_bound gwarantuje, iż w przypadku znalezienia poszukiwanej wartości, otrzymamy iterator do pierwszego wystąpienia powtarzającego się elementu
