W niniejszym artykule poznasz wyszukiwanie binarne - jeden z najprostszych do napisania algorytmów wyszukujących dany element w dużym zbiorze 🌟. Nie tylko dowiesz się jakie są wady i zalety, lecz także jakie warunki muszą zostać spełnione, aby zadziałało to w sposób oczekiwany 🎯! A na deser, dostaniesz w pełni działający kod źródłowy 🍨! Zapraszam, bez ściemy 😄!
WYSZUKIWANIE BINARNE O WIELE SPRYTNIEJSZYM PODEJŚCIEM DO SZUKANIA ELEMENTU
Częstym dylematem z jakim będziesz miał(a) do czynienia będzie sytuacja, w której dysponujesz jakimś zbiorem danych (np. tablicą albo listą) i zależy Ci 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 o sytuacji, gdy mamy ich dziesiątki tysięcy 💪! Wtedy nie będziemy sprawdzać wszystkich elementów po kolei, bo stałoby się to dla procesora bardzo zasobożerne i niepraktyczne ❌.
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 "wyszukiwanie binarne" (ang. binary search) 💡.
ZASADA DZIAŁANIA
Technika wyszukiwania binarnego 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 przeszukania 🔍.
Następnie, na podstawie minimalnej i maksymalnej "granicy" przedziału, pobieramy środkowy indeks i badamy element "leżący" na tym indeksie. Jeżeli wartość tego elementu zgadza się z podanym w parametrze kryterium (np. obie liczby całkowite są sobie równe), algorytm dochodzi do wniosku, że to jest szukany element, zwraca wynik i kończy działanie ✅.
Jeżeli okaże się, że to nie jest ten element którego szukamy, to "obcinamy" połowę przedziału liczbowego, uznając że skoro sprawdzony element nie posiada wartości której szukamy, to dalszy (lub poprzedni) ciąg elementów także nie będzie go posiadać 🔥. W tym momencie aktualizujemy środkowy indeks, który zależy od tego, czy wartość poszukiwana jest większa lub mniejsza od zbadanej wartości ⚠️. Działa to tak 👇:
- jeżeli zbadana wartość jest mniejsza od poszukiwanej, to minimalny zakres będzie równy środkowemu indeksowi (przemieszczamy się w prawą stronę),
- jeżeli zbadana wartość jest większa od poszukiwanej, to maksymalny zakres będzie równy środkowemu indeksowi (przemieszczamy się w lewą stronę).
Dlatego warunkiem koniecznym jest operowanie na posortowanym zbiorze danych 🚨!
Wyszukiwanie binarne powtarza tę samą czynność od weryfikowania do "przycinania" granicy, aż do znalezienia elementu lub nie 🔍. Poszukiwania zostają przerwane w momencie, gdy początek przedziału "styka się" z jego końcem (indeks początku przedziału równa się indeksowi końca przedziału) i nie ma jak już skrócić 🙂.
 |
Algorytm wyszukiwania binarnego polega na poszukiwaniu wskazanego elementu "przycinając" każdorazowo zakres uwzględnianych indeksów i sprawdzając środek przedziału.
Nazwa pochodzi od przebiegu postępowania algorytmu ℹ️. Za każdym razem gdy stwierdza, że dany element nie jest tym, którego szukamy, dzielimy przedział poszukiwań na pół. Oczywiście może wystąpić przypadek dzielenia z ułamkiem (lecz wtedy dochodzi do "obcinania" wartości) i nie zawsze podzielimy ten zakres dokładnie o połowę 😊, natomiast takie jest znaczenie wyszukiwania binarnego 💡.
ZŁOŻONOŚĆ OBLICZENIOWA
Wyszukiwanie binarne charakteryzuje się następującą złożonością obliczeniową (złożoności obliczeniowe algorytmów zwykle określa się tzw. "notacją dużego O") 👇:
O(log(n)) : n = rozmiar zbioru danych
W wolnym tłumaczeniu: logarytm z rozmiaru zbioru danych przy podstawie 2 💥. To dlatego, iż za każdym razem dochodzi do skrócenia liczby elementów do sprawdzenia o połowę.
Przykładowo, dla 100 elementów wychodzi w najgorszym razie 7 weryfikacji 😮! Porównując to do wyszukiwania "klasycznego" (jeden element po drugim), tam wyszłoby 100 iteracji 😱!
W notacji dużego O jest taki zwyczaj, że jeśli jest samo oznaczenie logarytmu bez podstawy, to w domyśle podstawą jest 2. Czyli:
log = log2
KOD ŹRÓDŁOWY
A teraz gotowy kod w języku Java prezentujący wyszukiwanie binarne w akcji 🎬!
KLASA "MAIN"
public class Main {
public static void main(String[] args) {
new BinarySearch();
}
}Tu mamy nasz "start" programu, czyli klasę uruchomieniową "Main" i wywoływanie konstruktora klasy inicjującej cały algorytm ▶️. Opis tej klasy zostawiam na koniec, aby na razie skupić się na pozostałych budulcach 😉.
KLASA "INTEGERSLIST"
import java. util.ArrayList;
public class IntegersList extends ArrayList<Integer> {
public IntegersList(int size, int step) {
addNumbersWithStep(size, step);
}
private void addNumbersWithStep(int size, int step) {
if(step < 1) {
return;
}
for (int i = 1; i <= size; ++i) {
add(i*step);
}
}
}Ta klasa służy jako wygodne "opakowanie" prostego utworzenia listy liczb całkowitych "przeskakujących" o N, czyli np. co 2, co 3 itd. Zobacz, że korzystam z dziedziczenia po "ArrayList", dzięki czemu mogę skorzystać z gotowej implementacji metody "add", co pozwala na znaczne skrócenie kodu ✅. A dodawanie "sekwencji" liczb zawdzięczamy pętli "for" 😁!
KLASA "INTEGERRANGE"
public class IntegerRange {
private int minimum;
private int maximum;
public IntegerRange(int minimum, int maximum) {
setMinimum(minimum);
setMaximum(maximum);
}
public void setMinimum(int minimum) {
if(minimum <= maximum) {
this.minimum = minimum;
}
}
public void setMaximum(int maximum) {
if(maximum >= minimum) {
this.maximum = maximum;
}
}
public int getMinimum() {
return minimum;
}
public int getMaximum() {
return maximum;
}
public int getMiddleValue() {
return (minimum + maximum) / 2;
}
}Kolejna klasa pomocnicza do zarządzania zakresem od do, czyli naszym "przedziałem" opisanym w części teoretycznej ⭐. Tutaj mamy dwie dane składowe do kontrolowania lewego i prawego końca przedziału oraz szereg następujących metod (idąc według kolejności od góry do dołu) 👇:
- konstruktor do ustawiania wartości początkowych,
- ustawianie minimalnej wartości,
- ustawianie maksymalnej wartości,
- pobieranie minimalnej wartości,
- pobieranie maksymalnej wartości,
- wyliczanie i pobieranie wartości środkowej.
Do metod modyfikujących przedział wprowadziłem instrukcje warunkowe, aby nie doszło do sprzecznej sytuacji ustawienia górnej granicy jako mniejszej od minimalnej i vice-versa ⚠️.
Do wyliczania środka przedziału, dzielimy 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 😅.
KLASA "RESULTSPRINTER"
import java. io.PrintStream;
import java. util.List;
public class ResultsPrinter {
private final PrintStream printStream = System.out;
public void printNumberAtIndex(List<Integer> list, int index) {
printStream.println("Liczba " + list.get(index) + " znajduje się pod indeksem " + index);
}
}A tu mamy klasę jedynie do wypisywania rezultatu czy wyszukiwanie binarne znalazło poszukiwany element, czy też nie 📝. W obu przypadkach, wynik zostanie wyświetlony. Wydzieliłem to w taki sposób, abyś mógł/mogła łatwo usunąć to z kodu, gdyby to Ci nie było potrzebne 😄.
KLASA "BINARYSEARCH"
import java. util.ArrayList;
public class BinarySearch {
private final ResultsPrinter resultsPrinter = new ResultsPrinter();
public BinarySearch() {
var numbers = new IntegersList(100, 3);
var indexOfSearchedNumber = getIndexOfSearchedNumber(numbers, 69);
resultsPrinter.printNumberAtIndex(numbers, indexOfSearchedNumber);
}
private int getIndexOfSearchedNumber(ArrayList<Integer> numbers, int searchedNumber) {
if(numbers == null) {
return -1;
}
var integerRange = new IntegerRange(0, numbers.size());
while (integerRange.getMinimum() < integerRange.getMaximum()) {
var middleIndex = integerRange.getMiddleValue();
var numberInMiddleIndex = numbers.get(middleIndex);
if(numberInMiddleIndex == searchedNumber) {
return middleIndex;
} else if(numberInMiddleIndex < searchedNumber) {
integerRange.setMinimum(middleIndex);
} else {
integerRange.setMaximum(middleIndex);
}
}
return -1;
}
}No i jesteśmy w klasie z algorytmem 😊. Wyjaśniam co, jak i przede wszystkim dlaczego.
Po wejściu do konstruktora klasy, definiowane są dwie zmienne lokalne (korzystam ze słowa "var", które pozwala uniknąć wstawiania typu danych) 👇:
- lista z liczbami całkowitymi tworzona przy użyciu naszej klasy "IntegersList",
- indeks poszukiwanej przez nas liczby całkowitej jako wynik działania wyszukiwania binarnego.
Ostatnia instrukcja wypisuje na terminalu wynik działania (jeżeli nie potrzebujesz wypisywania wyniku, możesz to usunąć z kodu 🙂). Druga metoda to nasz algorytm wyszukiwania binarnego i teraz go opiszę 💣!
Pierwszą rzeczą jest sprawdzenie czy w ogóle została zdefiniowana lista przekazywana do parametru (jeżeli jest równe "null", to zwracamy od razu -1). Następnie, definiujemy nasz "przedział liczbowy" (od do), zgodnie z notacją indeksową:
- minimum = zero,
- maksimum = rozmiar listy pomniejszony o jeden.
Wchodzimy do pętli "while" wewnątrz której, osadzamy warunek, czy końce granicy nie nachodzą na siebie (minimum >= maksimum). Jeżeli nie, to program wchodzi do środka i definiuje 2 kolejne liczby całkowite:
- indeks środka przedziału,
- wartość elementu w liście pod indeksem w środku przedziału.
Głównym punktem programu jest instrukcja warunkowa. Wyszukiwanie binarne sprawdza dany element i jeżeli to jest nasz poszukiwany, to zwraca wyliczony środkowy indeks przy pomocy "return" i zamyka sprawę ☑️.
Jeżeli jednak jest "passe", to skraca przedział liczbowy od jednej ze stron (warunki "else if" i "else") i szuka dalej 🔍. Albo od lewej strony (gdy liczba znajdująca się pod środkowym indeksem jest mniejsza od poszukiwanego), albo od prawej (gdy liczba znajdująca się pod środkowym indeksem jest większa od poszukiwanego) 🔥.
Algorytm powtarza te czynności, aż do znalezienia wartości, lecz może dojść do przyrównania lewej strony granicy do prawej, co będzie oznaczało, że nie ma już czego szukać, więc zwracamy wartość -1, czyli taki umowny "null" (w języku Java nie ma ujemnych indeksów dla tablic i list).
Podsumowanie: 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 otrzymany wynik nie będzie prawidłowy ❌.
To by było tyle 👍. Zachęcam do uruchomienia programu i eksperymentowania samodzielnie 😉. Tylko tak zrozumiesz ten kod bez zapamiętywania 🧠!