W tym dwuczęściowym artykule omówimy sobie algorytm wyszukiwania binarnego (ang. binary search). Do tematu podejdziemy jednak bardziej po inżyniersku, bowiem zamiast samodzielnie implementować ten algorytm (bardziej szczegółowe omówienie tego algorytmu wraz z przykładową implementacją stanowi temat na osobny artykuł), przedstawie jak skorzystać z tego co oferuje nam biblioteka języka C++. Algorytm ten, w porównaniu do ”siłowej” metody (ang. brute force) o liniowej złożoności obliczeniowej O(N), cechuje się lepszą, logarytmiczną złożonością O(logN). Warunkiem koniecznym do zastosowania tego algorytmu jest uprzednie posortowanie przeszukiwanego zbioru danych. Algorytm ten może być zaimplementowany zarówno iteracyjnie jak i rekurencyjnie.
Jeżeli używasz systemu kontroli wersji Git, wówczas algorytmu wyszukiwania binarnego używasz wprost posługując się komendą git bisect. Jej celem jest szybkie znalezienie ”commita”, który wprowadził błąd (ang. bug). Dzięki temu podejrzany commit odnajdziesz najczęściej zaledwie w kilku krokach. Wyobraź sobie co by było gdybyś musiał w sposób liniowy przeszukiwać dziesiątki commitów, aby znaleźć ten jedyny, który okazał się przyczyną błędu…
W tej części skupię się na funkcji bsearch, która stanowi dziedzictwo biblioteki standardowej języka C. Natomiast przedmiotem rozważań w drugiej części będzie algorytm std::binary_search dostępny w bibliotece standardowej języka C++. Pokażę także jak można samodzielnie zaimplementować własną bardziej uniwersalną wersję tego algorytmu, wykorzystując gotowe komponenty w postaci algorytmów:
- std::lower_bound
- std::upper_bound
- std::equal_range
Funkcja bsearch
Podczas omawiania funkcji bsearch, przedstawię dwa przykłady wyszukiwania:
- liczby całkowitej typu int
- łańcucha tekstowego (c-string) reprezentowanego przez typ const char *
Interfejs funkcji bsearch przestawia się następująco:
void *bsearch (const void *key, const void *ptr, size_t count, size_t size,
int (*comp)(const void *, const void *));
Na pierwszy rzut oka interfejs ten nie wygląda na zbyt przejrzysty, tym bardziej, że mamy tu aż 5 parametrów, wśród których często pojawia się typ const void *. Ponadto typem zwracanym jest typ void *, który reprezentuje adres odnalezionego elementu lub NULL w przypadku jego braku. Oto kolejne parametry:
- key (typ const void *) – wskaźnik do stałej zawierającej poszukiwaną wartość – zauważ, że do funkcji bsearch nie możemy przekazać stałej w postaci literału, bowiem zawsze będziemy potrzebować jakiejś zmiennej lub stałej (przechowującej wzorcową wartość do znalezienia), aby przekazać jej adres (wskaźnik) do funkcji bsearch (inaczej mówiąc potrzebujemy tutaj l-wartości)
- ptr (typ const void *) – wskaźnik do stałej reprezentujący początek pamięci zajmowanej przez przeszukiwane dane – widoczne jest tutaj istotne ograniczenie w postaci wymogu ciągłego obszaru pamięci (w przypadku rozwiązań stosowanych w języku C++ to ograniczenie nie występuje ze względu na obecność iteratorów)
- count (typ size_t) – ilość elementów do przeszukiwania
- size (typ size_t) – rozmiar pojedynczego elementu w przeszukiwanej kolekcji danych
- comp (typ int (*)(const void *, const void *)) – wskaźnik do funkcji porównującej elementy kolekcji
Jak widać funkcja bsearch posiada pewne ograniczenia i niedogodności. Ograniczeniem na pewno jest wymóg ciągłości pamięci dla przeszukiwanego zbioru danych. Warto też zauważyć, że język C, w którym napisana została funkcja bsearch, w zasadzie nie posiada generycznych cech (dla porównania, w języku C++ rozwiązania generyczne są stosunkowo łatwe do osiągnięcia przede wszystkim dzięki szablonom oraz iteratorom). Jedyne minimum w tym zakresie zapewniają typy const void * oraz void * i dlatego występują tak często w interfejsie funkcji bsearch. Dotyczy to typu zwracanego (void *), typu parametrów key i ptr (const void *) oraz obu parametrów funkcji porównującej (const void *).
Funkcja qsort
Jak już wcześniej wspomniałem algorytm wyszukiwania binarnego wymaga na wejściu posortowanej kolekcji danych. W tym celu posłużymy się gotowym algorytmem w postaci funkcji qsort. która podobnie jak bsearch jest odziedziczona po bibliotece standardowej języka C. Implementacja ta oferuje algorytm szybkiego sortowania (ang. quick sort – stąd nazwa qsort). Jest to algorytm rekurencyjny, zgodny z zasadą ”dziel i zwyciężaj” (ang. divide and conquer). Interfejsy funkcji qsort i bsearch są bardzo podobne. Głowna różnica polega na tym, iż funkcja qsort z oczywistych względów nie posiada parametru key odpowiedzialnego w funkcji bsearch za dostarczenie wzorcowego elementu do wyszukania:
void qsort(void *ptr, size_t n, size_t size, int (*comp)(const void *, const void *));
Interpretacja parametrów jest praktycznie taka sama jak dla funkcji bsearch – jedynie wskaźnik ptr nie jest wskaźnikiem do stałej, ponieważ mamy tu do czynienia z algorytmem modyfikującym kolejność elementów w kolekcji danych. Ponadto funkcja qsort nie zwraca żadnej wartości (void). Aby skorzystać z obu algorytmów należy załączyć plik nagłówkowy stdlib.h / cstdlib.
To co jest ważne to fakt, iż obie funkcje wymagają parametru w postaci wskaźnika do funkcji porównującej (comp). Dzięki tej funkcji kolekcja danych może być posortowana w określony sposób (rosnąco lub malejąco). Po dostarczeniu odpowiedniej funkcji porównującej do funkcji qsort, funkcja bsearch powinna korzystać z tego samego mechanizmu porównywania elementów. W praktyce do obu funkcji najlepiej jest przekazać wskaźnik do tej samej funkcji porównującej. Na potrzeby naszych przykładów kolekcja danych będzie sortowana w porządku rosnącym (chyba że zostanie powiedziane inaczej).
Wyszukiwanie liczby całkowitej
Nasze rozważania rozpoczniemy od prostego przypadku wyszukiwania liczby całkowitej typu int. Dysponując niezbędną wiedzą przedstawioną w tym artykule możemy napisać przykładowy kod demonstrujący działanie funkcji bsearch (oraz przy okazji funkcji qsort):
#include <stdio.h>
#include <stdlib.h>
#define SIZEOF_ARRAY(array) (sizeof(array) / sizeof(*array))
int compare(const void *lhs, const void *rhs)
{
int l = *(const int *) lhs;
int r = *(const int *) rhs;
if (l < r) return -1;
if (l > r) return 1;
return 0;
}
int main()
{
int data[] = { 3, 7, 5, 8, 7, 2, 9, 4, 1, 6, 7, 0 };
size_t size = SIZEOF_ARRAY(data);
qsort(data, size, sizeof(int), compare);
for (size_t i = 0; i < size; ++i)
{
printf("%d ", data[i]);
}
printf("\n");
int val = 7;
int *ans = (int *) bsearch(&val, data, size, sizeof(int), compare);
if (ans != NULL)
printf ("%d found on index %td\n", *ans, (ans - data));
else
printf ("%d not found %d\n", val);
return 0;
}
0 1 2 3 4 5 6 7 7 7 8 9 7 found on index 9
Wskaźnik do odnalezionego elementu, zwracany przez funkcję bsearch, wykorzystano do odczytania jego pozycji (indeksu) w posortowanym zbiorze danych. W przypadku poszukiwania wartości, której nie ma w naszym zbiorze danych, otrzymamy następujący output:
0 1 2 3 4 5 6 7 7 7 8 9 10 not found 10
Zasadniczą rolę w naszym rozwiązaniu odgrywa funkcja porównująca compare:
int compare(const void *lhs, const void *rhs)
{
int l = *(const int *) lhs;
int r = *(const int *) rhs;
if (l < r) return -1;
if (l > r) return 1;
return 0;
}
Przedstawiona funkcja realizuje sortowanie w porządku rosnącym. Jeśli chcesz aby dane posortowane były w porządku malejącym wystarczy zamienić znaki relacji między dwoma argumentami:
int compare(const void *lhs, const void *rhs)
{
int l = *(const int *) lhs;
int r = *(const int *) rhs;
if (l > r) return -1;
if (l < r) return 1;
return 0;
}
Zobaczmy jak to wygląda w praktyce:
#include <stdio.h>
#include <stdlib.h>
#define SIZEOF_ARRAY(array) (sizeof(array) / sizeof(*array))
int compare(const void *lhs, const void *rhs)
{
int l = *(const int *) lhs;
int r = *(const int *) rhs;
if (l > r) return -1;
if (l < r) return 1;
return 0;
}
int main()
{
int data[] = { 3, 7, 5, 8, 7, 2, 9, 4, 1, 6, 7, 0 };
size_t size = SIZEOF_ARRAY(data);
qsort(data, size, sizeof(int), compare);
for (size_t i = 0; i < size; ++i)
{
printf("%d ", data[i]);
}
printf("\n");
int val = 7;
int *ans = (int *) bsearch(&val, data, size, sizeof(int), compare);
if (ans != NULL)
printf ("%d found on index %td\n", *ans, (ans - data));
else
printf ("%d not found %d\n", val);
return 0;
}
9 8 7 7 7 6 5 4 3 2 1 0 7 found on index 3
9 8 7 7 7 6 5 4 3 2 1 0 10 not found
Porównajmy jeszcze output dla przypadku znalezienia elementu w zależności od porządku sortowania:
0 1 2 3 4 5 6 7 7 7 8 9 7 found on index 9
9 8 7 7 7 6 5 4 3 2 1 0 7 found on index 3
Charakterystyczne jest to to, że w przypadku sortowania w porządku rosnącym otrzymaliśmy wskaźnik do ostatniego odnalezionego, powtarzającego się elementu. Natomiast w przypadku sortowania w porządku malejącym jest to wskaźnik do drugiego takiego elementu. Płynie z tego prawidłowy wniosek, że w przypadku gdy poszukiwany element występuje w kolekcji danych więcej niż jeden raz, funkcja bsearch nie gwarantuje który z tych elementów zostanie przez nią wskazany. Inaczej mówiąc, nie możemy zakładać, że otrzymany wskaźnik zawsze będzie odnosił się na przykład do pierwszego lub ostatniego wystąpienia elelemtu w posortowanej kolekcji danych (gwarancję otrzymania iteratora do pierwszego elementu zapewnia funkcja std::lower_bound, która stanowi podstawę omwianego w drugiej części artykułu algorytmu std::binary_search).
Wróćmy jeszcze na chwilę do funkcji porównującej:
int compare(const void *lhs, const void *rhs)
{
int l = *(const int *) lhs;
int r = *(const int *) rhs;
if (l < r) return -1;
if (l > r) return 1;
return 0;
}
Przedstawiona funkcja tylko z pozoru jest uniwersalna (obsługuje typy danych, dla których zdefiniowano operatory ”<” oraz ”>”), bowiem jak się wkrótce okaże takie rozwiązanie bywa niewystarczające. W przypadku liczb całkowitych, możemy zastosować pewne uproszczenie oparte na ich odejmowaniu (w przypadku różnych wartości porównywanych argumentów, znaczenie ma tutaj jedynie znak wartości zwracanej):
int compare(const void *lhs, const void *rhs)
{
int l = *(const int *) lhs;
int r = *(const int *) rhs;
return l - r;
}
Oto zmodyfikowany przykład:
#include <stdio.h>
#include <stdlib.h>
#define SIZEOF_ARRAY(array) (sizeof(array) / sizeof(*array))
int compare(const void *lhs, const void *rhs)
{
int l = *(const int *) lhs;
int r = *(const int *) rhs;
return l - r;
}
int main()
{
int data[] = { 3, 7, 5, 8, 7, 2, 9, 4, 1, 6, 7, 0 };
size_t size = SIZEOF_ARRAY(data);
qsort(data, size, sizeof(int), compare);
for (size_t i = 0; i < size; ++i)
{
printf("%d ", data[i]);
}
printf("\n");
int val = 7;
int *ans = (int *) bsearch(&val, data, size, sizeof(int), compare);
if (ans != NULL)
printf ("%d found on index %td\n", *ans, (ans - data));
else
printf ("%d not found\n", val);
return 0;
}
0 1 2 3 4 5 6 7 7 7 8 9 7 found on index 9
0 1 2 3 4 5 6 7 7 7 8 9 10 not found
Wyszukiwanie c-stringa
Wspomniałem wcześniej, iż funkcja porównująca oparta na operatorach ”<” i ”>” tylko z pozoru jest uniwersalna. Aby to udowodnić, tym razem posłużę się przykładem wyszukiwania c-stringa, który w naszej kolekcji danych reprezentowany jest przez typ const char *. Ponieważ jest to wskaźnik, nie będzie nam zależało na szukaniu łańcucha ze względu na jego adres w pamięci lecz na jego treść. Aby przedstawić ten problem zacznijmy więc od naiwnego (nieprawidłowego) rozwiązania, opartego na wspomnianej przed chwilą (pozornie uniwersalnej) funkcji porównującej:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZEOF_ARRAY(array) (sizeof(array) / sizeof(*array))
int compare(const void *lhs, const void *rhs)
{
const char *l = *(const char * const *) lhs;
const char *r = *(const char * const *) rhs;
if (l < r) return -1;
if (l > r) return 1;
return 0;
}
int main()
{
const char *data[] = {
"January",
"February",
"March",
"April",
"May",
"June",
"July",
"August",
"September",
"October",
"November",
"December"
};
size_t size = SIZEOF_ARRAY(data);
qsort(data, size, sizeof(const char *), compare);
for (size_t i = 0; i < size; ++i)
{
printf("%s\n", data[i]);
}
printf("\n");
const char *val = "July";
const char **ans = (const char **) bsearch(&val, data, size, sizeof(const char *), compare);
if (ans != NULL)
printf ("\"%s\" found on index %td\n", *ans, (ans - data));
else
printf ("\"%s\" not found\n", val);
return 0;
}
January
February
March
April
May
June
July
August
September
October
November
December
"July" found on index 6
Wydawać by się mogło, iż nasze rozwiązanie działa prawidłowo. Na szczęście output z nieprawidłowo posortowanego zbioru danych zdradza błąd, polegający na posortowaniu względem adresu pamięci, zamiast treści łańcucha tekstowego (tak naprawdę kolejność elementów nie zmieniła się, ponieważ literały tekstowe zostały umieszczone w pamięci w kolejności ich pojawienia się w kodzie źródłowym). Program poinformował nas o znalezieniu istniejącego łańcucha tekstowego ”July” przez przypadek, ponieważ literały tekstowe mają stałe określone adresy pamięci podczas wykonywania programu. Zastąpmy teraz literał tekstowy zmienną tablicową July przechowującą tę samą treść (”July”):
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZEOF_ARRAY(array) (sizeof(array) / sizeof(*array))
int compare(const void *lhs, const void *rhs)
{
const char *l = *(const char * const *) lhs;
const char *r = *(const char * const *) rhs;
if (l < r) return -1;
if (l > r) return 1;
return 0;
}
int main()
{
const char *data[] = {
"January",
"February",
"March",
"April",
"May",
"June",
"July",
"August",
"September",
"October",
"November",
"December"
};
size_t size = SIZEOF_ARRAY(data);
qsort(data, size, sizeof(const char *), compare);
for (size_t i = 0; i < size; ++i)
{
printf("%s\n", data[i]);
}
printf("\n");
const char July[] = "July";
const char *val = July;
const char **ans = (const char **) bsearch(&val, data, size, sizeof(const char *), compare);
if (ans != NULL)
printf ("\"%s\" found on index %td\n", *ans, (ans - data));
else
printf ("\"%s\" not found\n", val);
return 0;
}
January
February
March
April
May
June
July
August
September
October
November
December
"July" not found
Teraz widać istotę problemu. Wyszukiwanie względem adresu w pamięci tym razem nie powiodło się (zgodnie z oczekiwaniami), kiedy przekazaliśmy do funkcji porównującej inny adres w pamięci, niż ten pod którym znajduje się literał tekstowy – pomimo tego iż treść obu łańcuchów tekstowych jest taka sama (”July”).
Teraz pora na prawidłowe rozwiązanie. W tym celu zmodyfikujemy naszą funkcję porównującą korzystając z gotowej funkcji strcmp, która wykona porównanie leksykograficzne. Naszym zadaniem będzie jedynie odpowiednie przekazanie argumentów funkcji porównującej do funkcji strcmp. Nasza funkcja porównująca będzie teraz wyglądać następująco:
int compare(const void *lhs, const void *rhs)
{
const char *l = *(const char * const *) lhs;
const char *r = *(const char * const *) rhs;
return strcmp(l, r);
}
Ponownie zobaczmy jak nasze rozwiązanie działa w praktyce:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZEOF_ARRAY(array) (sizeof(array) / sizeof(*array))
int compare(const void *lhs, const void *rhs)
{
const char *l = *(const char * const *) lhs;
const char *r = *(const char * const *) rhs;
return strcmp(l, r);
}
int main()
{
const char *data[] = {
"January",
"February",
"March",
"April",
"May",
"June",
"July",
"August",
"September",
"October",
"November",
"December"
};
size_t size = SIZEOF_ARRAY(data);
qsort(data, size, sizeof(const char *), compare);
for (size_t i = 0; i < size; ++i)
{
printf("%s\n", data[i]);
}
printf("\n");
const char July[] = "July";
const char *val = July;
const char **ans = (const char **) bsearch(&val, data, size, sizeof(const char *), compare);
if (ans != NULL)
printf ("\"%s\" found on index %td\n", *ans, (ans - data));
else
printf ("\"%s\" not found\n", val);
return 0;
}
April
August
December
February
January
July
June
March
May
November
October
September
"July" found on index 5
W przypadku nie znalezienia szukanego elementu otrzymamy spodziewany output:
April
August
December
February
January
July
June
March
May
November
October
September
"Lipiec" not found
Oczywiście aby zrealizować przeszukiwanie w oparciu o kolekcję posortowaną malejąco wystarczy zamienić argumenty dla funkcji strcmp:
int compare(const void *lhs, const void *rhs)
{
const char *l = *(const char * const *) lhs;
const char *r = *(const char * const *) rhs;
return strcmp(r, l);
}
Na styku języka C i C++
Jak widzisz wszystkie dotychczasowe przykłady zostały napisane w ”czystym” języku C. W drugiej części tego artykułu przedstawię rozwiązania zaimplementowane w języku C++. Mam nadzieję, że dzięki temu będziesz mógł łatwiej porównać oba podejścia do używania gotowej implementacji algorytmu wyszukiwania binarnego. Na zakończenie tego artykułu chciałbym jeszcze zaprezentować nietypowe podejście łączące użycie funkcji qsort i bsearch z elementem nowoczesnego języka C++ czyli wyrażeniem lambda. Jak już wiemy obie funkcje przyjmują wskaźnik do funkcji porównującej. Rozwiązanie oparte na wskaźniku do funkcji pochodzi z języka C i może wydawać się przestarzałe. Okazuje się jednak, iż nie przeszkadza to w połączeniu starej technologii czyli wskaźnika do funkcji z dużo nowszą technologią w postaci wyrażenia lambda (w rzeczywistości jest to obiekt funkcyjny), które pojawiło się w stadrdzie C++11. Jest możliwe dzięki niejawnej konwersji wyrażenia lambda na wskaźnik do funkcji. Nie wdając się zbytnio w szczegóły (wyrażenie lambda to temat na odrębny zestaw artykułów), aby taka konwersja była możliwa, wyrażenie lambda (ang. lambda expression) musi posiadać pustą listę przechwytującą (ang. capture list). Oto kod źródłowy przedstawiający to połączenie:
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <algorithm>
#define SIZEOF_ARRAY(array) (sizeof(array) / sizeof(*array))
int main()
{
// Lambda expression
auto compare = [](const void *lhs, const void *rhs)
{
int l = *static_cast<const int *>(lhs);
int r = *static_cast<const int *>(rhs);
return l - r;
};
int data[] = { 3, 7, 5, 8, 7, 2, 9, 4, 1, 7, 6, 0 };
size_t size = SIZEOF_ARRAY(data);
qsort(data, size, sizeof(int), compare);
copy(std::begin(data), std::end(data), std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
int val = 7;
auto ans = static_cast<int *>(bsearch(&val, data, size, sizeof(int), compare));
if (ans != nullptr)
std::cout << *ans << " found on index " << (ans - data) << '\n';
else
std::cout << val << " not found\n";
}
0 1 2 3 4 5 6 7 7 7 8 9 7 found on index 9
0 1 2 3 4 5 6 7 7 7 8 9 10 not found
Podsumowanie
- Wyszukiwanie binarne jest algorytmem o złożoności O(logN), który może być zaimplementowany na różne sposoby (zarówno iteracyjnie jak i rekurencyjnie)
- Algorytm wyszukiwania binarnego wymaga uprzedniego posortowania przeszukiwanego zbioru danych
- Jedna z implementacji algorytmu wyszukiwania binarnego ma postać funkcji bsearch będącej dziedzictwem biblioteki standardowej języka C
- Aby posortować dane, można użyć algorytmu qsort (szybkie sortowane), którego pochodzenie również sięga biblioteki standardowej języka C
- Funkcja bsearch i qsort oparta jest na mechanizmie funkcji porównującej, która w przypadku obu funkcji powinna zachowywać się tak samo (teoretycznie mogą to być różne funkcje, ale rezultat ich porównania musi być taki sam)
- Funkcja bsearch może być użyta wyłącznie z posortowanymi danymi wejściowymi znajdującymi się w ciągłym obszarze pamięci
- Używanie funkcji bsearch wymaga częstych rzutowań (ang. cast) z typu const void * (typ parametrów key i ptr oraz parametrów funkcji porównującej) lub void * (typ wartości zwracanej) na docelowy typ danych
- Typy const void * i void * zapewniają funkcji bsearch ”minimalną generyczność” w stylu języka C
- Funkcja bsearch zwraca wskaźnik do odnalezionego elementu, co umożliwia m.in. odczytanie jego pozycji (indeksu) w posortowanej kolekcji danych
- W przypadku odnalezienia elementu który występuje więcej niż jeden raz funkcja bsearch nie gwarantuje, który z tych elementów zostanie wskazany (wskaźnik void * zwracany przez funkcję bsearch) – wpływ na to może mieć chociażby sposób posortowania przeszukiwanych danych (rosnący lub malejący)
- Zwracaj szczególną uwagę na implementację funkcji porównawczej, a rozwiązania pozornie uniwersalne stosuj z rozwagą
- Wskaźnik do funkcji porównującej, może być zastąpiony przez wyrażenie lambda (zachodzi niejawna konwersja wyrażenia lambda na wskaźnik do funkcji pod warunkiem, że lista przechwytująca tego wyrażenia jest pusta)
