Strona główna » Algorytmy » Wyszukiwanie » Wyszukiwanie binarne
 

Wyszukiwanie binarne

https://mattomatti.com/fp02

Wyszukiwanie binarne

Wyszukiwanie binarne jest to algorytm, który potrafi wyszukać w krótkim czasie żądany element. Przeszukiwana tablica musi być posortowana. Algorytm polega na zawężaniu zakresu gdzie może znajdować się szukany element. Na początku algorytm porównuje poszukiwany element z elementem pośrodku przeszukiwanego zakresu. W przypadku braku takiego elementu przyjmuje się, że porównujemy z jednym z elementów prawie po środku. Jeśli szukany element jest większy od wybranej liczby a to przeszukujemy zakres tablicy po prawej strony. W każdym kolejnym kroku zmniejszamy zakres dwa razy, aż nie natrafimy na żądany element.

Dzielenie przeszukiwanego zakresu na dwa w każdym kolejnym kroku pozwala na uzyskanie złożoność czasowej rzędu Θ(log2n). Oznacza to, że dla tablicy długości 1000 sprawdzimy maksymalnie 10 znaków, ponieważ log21000 = 9.9657... ≈ 10. Z kolei dla tablicy długości 1,000,000,000 elementów porównamy zaledwie 30 elementów! Jak widać oszczędność czasowa jest tu znacząca. Tak samo jak w przypadku wyszukiwania liniowego złożoność pamięciowa wynosi Θ(1), ponieważ będziemy potrzebowali tylko kilka dodatkowych zmiennych.

Przykład

Załóżmy, że mamy posortowaną tablicę liczb całkowitych L:={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Naszym zadaniem jest wyznaczenia pozycji liczby 7:

LPLista z zakresuŚrodekKomentarz
110{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}5.5 ≈ 5piąty element to 5, nie jest to szukana i jest mniejszy od szukanej, więc sprawdzamy zakres po prawej stronie
610{6, 7, 8, 9, 10}8ósmy element to 8, nie jest to szukana i jest większa od szukanej, więc sprawdzamy zakres po lewej stronie
67{6, 7}6.5 ≈ 6szósty element to 6, nie jest to szukana i jest mniejsza od szukanej, więc sprawdzamy zakres po prawej stronie
77{7}7siódmy element to 7, jest to szukana, zwracamy indeks 7

Szukaną wartość znaleźliśmy na pozycji numer 7.

Implementacja

Funkcja wyszukaj() realizująca algorytm wyszukiwania binarnego przyjmuje 3 argumenty: lista - posortowana lista na której należy znaleźć element, n - ile jest elementów na liście oraz szukana - element do wyszukiwania.

  1. int wyszukaj(double* lista, int n, double szukana){
  2.   int L = 0, P = n - 1, sr = 0;
  3.   while (L <= P){
  4.     sr = (L + P) / 2;
  5.     if(lista[sr] == szukana)
  6.       return sr;
  7.     if(lista[sr] > szukana)
  8.       P = sr - 1;
  9.     else
  10.       L = sr + 1;
  11.   }
  12.   return -1;
  13. }

(1.) Nasza funkcja wyszukaj() przyjmuje trzy argumenty: lista - tablicę zawierającą posortowane elementy. W tym przypadku jest to tablica posortowanych liczb rzeczywistych. Funkcja przyjmuje jeszcze n - długość tablicy oraz szukana - liczbę rzeczywistą, którą chcemy wyszukać. (2.) Na początek ustalamy zakres przeszukiwanego zakresu. W tym przypadku jest to [L, P] = [0, n - 1]. Deklarowane sr to środek przeszukiwanego zakresu. (3.) Dopóki L ≤ P to: (4.) obliczamy środek - jest to średnia arytmetyczna indeksu elementu pierwszego i ostatniego przeszukiwanego zakresu. (5.) Sprawdzamy czy na pozycji sr jest nasz poszukiwana liczba. Jeśli tak to (6.) zwracamy pozycję. Jeśli jednak nie to (7.) sprawdzamy czy element na pozycji sr jest większy od poszukiwanej liczby. Jeśli jest mniejszy to (8.) zmniejszamy zakres z prawej strony. W przeciwnym wypadku (10.) przesuwamy zakres z lewej strony. Jeśli wyjdziemy poza pętle while oznacza to, że w tablicy nie poszukiwanego elementu czyli (12.) zwracamy -1. Będzie to oznaczało, że dany element nie istnieje.

Implementacja rekurencyjna

Na początek zadeklarujemy funkcją pomocniczą, która będzie odpowiadała za wyszukiwanie. Potem napiszemy główną funkcję wyszukaj():

  1. int wyszukaj_pom(double* lista, double szukana, int L, int P){
  2.   int sr = (L + P) / 2;
  3.   if(lista[sr] == szukana)
  4.     return sr;
  5.   if(L >= P)
  6.     return -1;
  7.   if(lista[sr] > szukana)
  8.     return wyszukaj_pom(lista, szukana, L, sr -1);
  9.   return wyszukaj_pom(lista, szukana, sr + 1, P);
  10. }

(1.) Tym razem przyjmujemy cztery argumenty: lista - tablica do przeszukania, szukana - element do znalezienia, L i P - odpowiednio lewy i prawy indeks zakresu. (2.) Wyliczamy środek zakresu. (3.) Jeśli środkowy element jest równy szukanemu to (4.) zwracamy indeks sr. (5.) Jeśli L = P i nie zwróciliśmy wyniku oznacza to, że dany element nie istnieje. Wtedy (6.) zwracamy -1. (7.) Jeśli nie znaleźliśmy poszukiwanej wartości oraz L ≠ P to zmieniamy zakres wywołując funkcję z odpowiednimi parametrami i zwracając (8. - 9.) odpowiedni wynik.

  1. int wyszukaj(double* lista, int n, double szukana){
  2.   return wyszukaj_pom(lista, szukana, 0, n-1);
  3. }

Teraz nasz funkcja zbiega się tylko do jednej linijki. Jej nagłówek jest zgodny z poprzednią implementacją. Jednak (1.) tym razem zwracamy wynik funkcji wyszukaj_pom() dla zakresu [L, P] = [0, n - 1]. Warto zwrócić uwagę, że tym razem nie przekazujemy dalej wartości n. Nie ma takiej potrzeby, ponieważ nie wyjdziemy poza zakres w funkcji wyszukaj_pom(), dzięki ustaleniu wartości L i P.

Testowanie funkcji

Obydwie funkcje możemy przetestować używając poniższej funkcji main().

  1. int main () {
  2.   int n;
  3.   cin >> n;
  4.   double* L = new double[n];
  5.   for(int i = 0; i < n; i++)
  6.     cin >> L[i];
  7.   double szukana = 0;
  8.   cin >> szukana;
  9.   cout << wyszukaj(L, n, szukana) << endl;
  10.   delete[] L;
  11.   system("pause");
  12.   return 0;
  13. }