Jakub Piskorowski on 07/04/2022 wersja: 1.0
Przedstawienie działania algorytmu wyszukiwania binarnego
Kod źródłowy: wyszukiwanie-binarne.cpp
📗 Poziom 2
Powrót do Algorytmy wyszukiwania
Algorytm szuka danego elementu w tablicy uporządkowanej (posortowanej). Jest realizowany metodą "dziel i zwyciężaj". Dzieli on tablicę na mniejsze podtablice do momentu wyszukania pozycji (lub nie w przypadku gdy taki element nie istnieje) elementu szukanego.
Przeanalizujmy następujący zbiór 8 uporządkowanych liczb:
1 2 5 8 9 11 15 20
Potrzebne będą nam trzy zmienne pomocnicze:
l − przechowuje numer lewego krańca tablicy,
r − przechowuje numer prawego krańca tablicy,
sr − przechowuje numer środkowego elementu tablicy.
W pierwszym kroku algorytmu ustawiamy:
int l = 0;
int p = 7;
int sr = (l+p)/2;A więc mamy:
Następnie sprawdzamy czy szukany element znajduje się na pozycji sr. Jeśli tak to znaleźliśmy daną liczbę, w przeciwnym przypadku sprawdzamy czy szukana liczba jest mniejsza czy większa niż liczba znajdująca się na środkowej pozycji.
Jeśli jest mniejsza, tzn., że mamy do przeszukania lewą część badanej tablicy. Zmieniamy wartość zmiennej.
p = sr−1
a więc:
W przypadku gdy jest większa to przeszukujemy prawą część tablicy. Zmieniamy wartość zmiennej l na:
l = sr + 1
a więc:
Czynność tą powtarzamy do momentu znalezienia szukanej wartości, lub gdy zmienne l i r spełnią warunek: l > r. W takim przypadku element nie występuje w zbiorze liczb.
Wejście:
szukana - poszukiwana liczba
tab[15] - tablica z posortowanymi wartościami (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47)
Wyjście:
pozycja - indeks (pozycja) tablicy na której znajduje się poszukiwana wartość
Zmienne pomocnicze:
l − przechowuje indeks lewego krańca tablicy,
p − przechowuje indeks prawego krańca tablicy,
sr − przechowuje indeks środkowego elementu tablicy
Lista kroków:
K1: l ← 0
K2: p ← 15
K3: sr ← (l+p)/2
K4: Dopóki l <= p
wykonuj kroki od K5 do K7
K5: Jeśli tab[sr] = szukana
zwróć sr
K6: Jeśli tab[sr] > szukana
to p ← sr - 1
inaczej l ← sr + 1
K7: sr ← (l+p)/2
K8: zwróć -1
Wynik działania programu:
Podaj liczbe ktora chcesz znalezc: 29
Liczba 29 wystepuje w zbiorze w komorce o indeksie 9
Kod źródłowy: wyszukiwanie-binarne.cpp