W niniejszym artykule poznacie wyszukiwanie binarne, jeden z najprostszych do napisania algorytmów wyszukujących dany element w dużym zbiorze. Skończy się nie tylko na kodzie źródłowym, ale także dowiecie się jakie są wady i zalety, a także pod jakimi warunkami zadziała to w sposób oczekiwany. Zapraszam, bez ściemy!
| Tweet |
WYSZUKIWANIE BINARNE O WIELE BARDZIEJ INTELIGENTNYM PODEJŚCIEM DO SZUKANIA ELEMENTU
Częstym dylematem z jakim będziecie mieli do czynienia będzie sytuacja, w której dysponujecie jakąś tablicą albo listą i zależy Wam na odszukaniu elementu o podanym kryterium (np. liczby). Nie uwzględniamy przypadku posiadania kilkunastu elementów, bo to można zrobić na piechotę, tylko pomyślmy raczej co zrobić kiedy mamy ich dziesiątki tysięcy. "Ło, panie!". Chyba nie będziemy wtedy sprawdzać wszystkich elementów po kolei, bo stałoby się to dla procesora bardzo zasobożerne. Zatem powstaje problem algorytmiczny o takiej postaci:
Problem: znalezienie położenia (indeksu) elementu w posortowanym zbiorze danych o podanym kryterium (najczęściej liczbowym) przy jak najmniejszej liczbie iteracji (powtórzeń)
Do rozwiązania tak postawionego problemu elegancko pasuje "binary search", czyli po polsku "wyszukiwanie binarne". Technika polega na tym, że dysponując POSORTOWANĄ tablicą lub listą (dalej wyjaśniam dlaczego elementy muszą być posortowane), zaznaczamy sobie przedział liczbowy od którego do którego indeksu należy uwzględniać obszar przeszukiwania. Na podstawie minimalnej i maksymalnej "granicy" przedziału, pobiera się środkowy indeks i badany jest element "leżący" na tym indeksie. Jeżeli wartość tego elementu zgadza się z podanym w parametrze kryterium (np. obie liczby całkowite są ze sobą zgodne), algorytm dochodzi do wniosku że to jest szukany element i kończy działanie.
Kiedy jednak to nie jest ten element, wyszukiwanie binarne "obcina" połowę przedziału liczbowego, uznając że skoro sprawdzony element nie posiada szukanej wartości, to dalszy (lub poprzedni) ciąg elementów także go nie będzie posiadać. W zależności od tego, czy wartość parametru jest większa lub mniejsza od zbadanej wartości, program przypisze wartość środkowego indeksu zmiennej kontrolującej kolejno lewą, bądź prawą granicę obszaru do przeszukiwania (stąd warunkiem koniecznym jest posortowany zbiór danych). Algorytm powtarza tę czynność od weryfikowania do "przycinania" granicy, aż do znalezienia elementu lub wystąpienia sytuacji, w której początek przedziału będzie stykał się z jego końcem (wartość zmiennej dla początku przedziału będzie równa wartości zmiennej dla końca przedziału) i nie ma jak już tego skrócić, więc uzna że nie znaleziono elementu.
 |
Algorytm wyszukiwania binarnego polega na poszukiwaniu wskazanego elementu "przycinając" każdorazowo zakres uwzględnianych indeksów i sprawdzając środek przedziału.
Pochodzenie nazwy? Są dwa racjonalne wytłumaczenia. Pierwsze jest takie, że za każdym razem dzielimy przedział szukania indeksu na pół z lewej lub prawej strony, zatem pojawia się decyzja którą drogą pójść (lewo / prawo). Drugie znaczenie wskazuje także na podejmowanie decyzji "zerojedynkowej", tylko już w kontekście identyfikacji elementu czy jest to ten, którego szukamy (tak / nie).
ZŁOŻONOŚĆ OBLICZENIOWA
Wyszukiwanie binarne charakteryzuje się złożonością obliczeniową O(log(n)), gdzie n oznacza rozmiar tablicy / listy. Jest to logarytm z rozmiaru zbioru danych przy podstawie 2. Dzieje się tak dlatego, iż za każdym razem dochodzi do skracania liczby elementów do sprawdzenia o połowę co iterację. W efekcie czego, dla stu elementów wychodzi w najgorszym razie 7 weryfikacji zamiast 100 i do widzenia! Prawda, że robi różnicę?
W notacji dużego O jest taki zwyczaj, że jeśli jest samo oznaczenie logarytmu bez podstawy, to w domyśle podstawą jest dwójka. Krótko:
log = log2
O samej notacji dużego O będzie więcej informacji w osobnym artykule. Nie chcę mieszać obu wątków.
KOD ŹRÓDŁOWY
A oto kodzik napisany w samej Javie prezentujący wyszukiwanie binarne w akcji:
KLASA "MAIN"
public class Main {
public static void main(String[] args) {
new BinarySearch();
}
}KLASA "NUMBERSLIST"
import java. util.ArrayList;
public class NumbersList extends ArrayList<Integer> {
public NumbersList(int size, int multiplier) {
addNumbers(size, multiplier);
}
private void addNumbers(int size, int multiplier) {
for (int i = 1; i <= size; ++i) {
add(i*multiplier);
}
}
}KLASA "LAUNCHER"
import java. util.ArrayList;
public class BinarySearch {
public Launcher() {
NumbersList numbersList = new NumbersList(100, 3);
int number = 69;
System.out.println("Liczba " + number + " została znaleziona na indeksie " + binarySearch(numbersList, number));
}
private int binarySearch(ArrayList<Integer> numbers, int number) {
int minIndex = 0;
int maxIndex = numbers.size() - 1;
while (minIndex < maxIndex) {
int middleIndex = (minIndex + maxIndex) / 2;
int guess = numbers.get(middleIndex);
if(guess == number) {
return middleIndex;
} else if(guess < number) {
minIndex = middleIndex;
} else {
maxIndex = middleIndex;
}
}
return -1;
}
}Wyjaśniam co, jak i przede wszystkim dlaczego. Po wejściu do konstruktora klasy "BinarySearch", w której umieściłem postać algorytmu, definiowane są dwie zmienne lokalne. Jedna typu "integer" dla szukanej przez nas liczby, a druga własnego typu dla naszego przykładowego zbioru danych. Dodałem pomocniczą klasę "NumbersList", aby oddzielić generowanie przykładowej posortowanej listy od meritum sprawy. W środku niej umieściłem bardzo prymitywne dodawanie numerków w kolejności rosnącej, żeby już nie robić z igły widły. Wracając do konstruktora, ostatnia instrukcja wypisuje na terminalu indeks, na którym ma znajdować się szukana liczba. Tu się zaczyna wyszukiwanie binarne.
Pierwszą rzeczą jest zdefiniowanie dwóch liczb całkowitych dla tej naszej "granicy" przedziału liczb, zgodnie z notacją indeksową. Minimum na początku zawsze jest zero, a maksimum, rozmiar tablicy lub listy pomniejszony o jeden. Wchodzimy do pętli "while" wewnątrz której osadzamy warunek, czy końce granicy nie nachodzą na siebie (minimum nie przekracza maksimum). Kiedy tak nie jest, program wchodzi do środka i na dzień dobry definiuje dwie kolejne liczby całkowite dla indeksu środka przedziału oraz liczby "stojącej" na tym indeksie. Korzystamy z operatora ilorazu do wyznaczenia środka przedziału dzieląc sumę końców przedziału na pół. Ponieważ obie wartości są typu "int", dojdzie do "obcięcia" części ułamkowej, w przypadku gdy wynik dzielenia będzie zmiennoprzecinkowy np. wyjdzie 14 zamiast 14.5, co będzie nam na rękę, bo indeks też musi być całkowitoliczbowy.
Głównym punktem programu jest złożona instrukcja warunkowa. Wyszukiwanie binarne jak wspomniałem, sprawdza dany element i jeśli jest on "passe", to skraca przedział liczbowy od jednej ze stron (warunki "else if" i "else"). Jeżeli to jest nasz poszukiwany, to zwraca wyliczony środkowy indeks przy pomocy "return" i zamyka sprawę. W przeciwnym razie gdy liczba znajdująca się pod wyliczonym indeksem jest mniejsza od poszukiwanego, przedział liczbowy jest "ścinany" od lewej strony (przypisz minimum wartość indeksu środka przedziału). A kiedy jest ona większa od szukanej, to skraca obszar od drugiej strony (przypisz maksimum wartość indeksu środka przedziału). Potem powtarza te czynności aż do znalezienia wartości, lecz może dojść do przyrównania lewej strony granicy do prawej, co w konsekwencji da sygnał algorytmowi, że nie ma takiego elementu i tu zwracamy wartość -1, czyli taki umowny "null" (w języku Java nie ma ujemnych indeksów dla tablic i list).
Podsumowując, wyszukiwanie binarne polega na ZNACZNIE efektywniejszym przeszukiwaniu POSORTOWANEJ tablicy lub listy z danymi i znajdowaniu elementu poszukiwanego. Warunkiem koniecznym do prawidłowego działania jest obowiązek posiadania elementów posortowanych według kolejności rosnącej. Inaczej będzie klops i złapiecie się za głowę jakie pierdoły Wam ten algorytm zwraca.
To by było tyle. Gorąco zachęcam do uruchomienia programu i eksperymentowania samodzielnie. A przede wszystkim ZROZUMCIE kod zamiast go zapamiętywać!