Wyszukiwanie binarne to algorytm służący do znajdowania pozycji elementu w posortowanej tablicy. Zamiast klasycznego sprawdzania kolejnych elementów tablicy, stosowana jest metoda „dziel i zwyciężaj”. Procedurę można opisać jako listę następujących czynności:

1. Sprawdź element znajdujący się w środku zbioru.

2. Jeśli sprawdzany element jest równy elementowi wyszukiwanemu, zwróć jego pozycję.

3. Jeśli sprawdzany element jest większy od szukanego, przeprowadź wyszukiwanie binarne w pierwszej połowie tablicy.

4. Jeśli sprawdzany element jest mniejszy od szukanego, przeprowadź wyszukiwanie binarne w drugiej połowie tablicy.

5. Wykonuj przedstawione czynności do momentu, w którym znajdziesz szukany element lub zabraknie nowych elementów do sprawdzenia.

Średnia złożoność czasowa wyszukiwania binarnego to $O(\log n)$, ponieważ $\log n$ to maksymalna liczba podziałów tablicy o $n$ elementach.

Uruchom aplet przedstawiający procedurę wyszukiwania binarnego. Wpisz wartość, która ma zostać wyszukana i naciśnij przycisk Wyszukaj. Sprawdź, jak program wykorzystujący algorytm wyszukiwania binarnego zachowa się dla różnych danych wejściowych.

Rq64vEsqGuhmQ1

Aplet składa się z ciągu liczb, przy czym każda z nich znajduje się w kwadratach. Elementy ciągu to kolejno: 1, 2, 4, 8, 9, 10, 17, 21, 25, 29, 31, 39, 49, 52, 62, 64, 76, 78, 80, 81, 88, 89. Mamy 23 wyrazy ciągu. Poniżej mamy nagłówek „Wartość:” i pole do wpisania żądanej wartości. Poniżej znajduje się przycisk z napisem „Wyszukaj”. Jeśli wartość żądana nie zostanie znaleziona, to pod polem do wpisywania pojawia się czerwony komunikat „Nie znaleziono wyrazu”. Algorytm szukania żądanej liczby działa w ten sposób, że dzieli ciąg na pół i wygasza tę część ciągu, do której żądana liczba nie należy. Połowę ciągu dzieli ponownie na pół i wygasza tę część, do której liczba nie należy i tak dalej aż do znalezienia liczby. Przykład działania algorytmu dla dla wartości 25. Wpisujemy w pole wartość 25 i klikamy „Wyszukaj”. Program zaznacza środkowy wyraz ciągu, czyli 39 w taki sposób, że podświetla na około sekundę obwód kwadratu na niebiesko. Wygasza liczby większe od 39. Mamy więc ciąg 1, 2, 4, 8, 9, 10, 17, 21, 25, 29, 31, 39. Następnie program podświetla środkowy wyraz nowego ciągu, czyli 10 i wygasza liczby mniejsze od 10. Teraz mamy ciąg 10, 17, 21, 25, 29, 31, 39. Program zaznacza środkowy wyraz, czyli 25. Liczba została znaleziona.

Aplet składa się z ciągu liczb, przy czym każda z nich znajduje się w kwadratach. Elementy ciągu to kolejno: 1, 2, 4, 8, 9, 10, 17, 21, 25, 29, 31, 39, 49, 52, 62, 64, 76, 78, 80, 81, 88, 89. Mamy 23 wyrazy ciągu. Poniżej mamy nagłówek „Wartość:” i pole do wpisania żądanej wartości. Poniżej znajduje się przycisk z napisem „Wyszukaj”. Jeśli wartość żądana nie zostanie znaleziona, to pod polem do wpisywania pojawia się czerwony komunikat „Nie znaleziono wyrazu”. Algorytm szukania żądanej liczby działa w ten sposób, że dzieli ciąg na pół i wygasza tę część ciągu, do której żądana liczba nie należy. Połowę ciągu dzieli ponownie na pół i wygasza tę część, do której liczba nie należy i tak dalej aż do znalezienia liczby. Przykład działania algorytmu dla dla wartości 25. Wpisujemy w pole wartość 25 i klikamy „Wyszukaj”. Program zaznacza środkowy wyraz ciągu, czyli 39 w taki sposób, że podświetla na około sekundę obwód kwadratu na niebiesko. Wygasza liczby większe od 39. Mamy więc ciąg 1, 2, 4, 8, 9, 10, 17, 21, 25, 29, 31, 39. Następnie program podświetla środkowy wyraz nowego ciągu, czyli 10 i wygasza liczby mniejsze od 10. Teraz mamy ciąg 10, 17, 21, 25, 29, 31, 39. Program zaznacza środkowy wyraz, czyli 25. Liczba została znaleziona.

Zasób interaktywny dostępny pod adresem https://zpe.gov.pl/a/DwY8eJarE

Uruchom aplet przedstawiający sortowanie przez kopcowanie (ang. heapsort). Jest to algorytm sortowania, którego złożoność czasowa w średnim i pesymistycznym przypadku wynosi $O(n \log n)$, gdzie $n$ to liczba danych do posortowania. Algorytm dzieli dane wejściowe na posortowaną i nieposortowaną część. Iteracyjne pobiera i usuwa z nieposortowanej części największy element, a następnie wstawia go do posortowanej części.

RjP4CliKamIr81

Aplet zatytułowany jest „Wizualizacja sortowania przez kopcowanie (Heapsort)”. Na białym prostokątnym polu znajdują się losowo rozrzucone punkty. W prawym górnym rogu znajdują się dwa przyciski: „Losuj” i „Sortuj”. Wciśnięcie przycisku „Losuj” powoduje przemieszanie punktów i ponowne losowe ich rozmieszczenie. Kliknięcie przycisku „Sortuj” powoduje uporządkowanie punków tak, że tworzą one przekątną pola biegnącą od prawego dolnego rogu do lewego górnego rogu prostokątnego pola.

Aplet zatytułowany jest „Wizualizacja sortowania przez kopcowanie (Heapsort)”. Na białym prostokątnym polu znajdują się losowo rozrzucone punkty. W prawym górnym rogu znajdują się dwa przyciski: „Losuj” i „Sortuj”. Wciśnięcie przycisku „Losuj” powoduje przemieszanie punktów i ponowne losowe ich rozmieszczenie. Kliknięcie przycisku „Sortuj” powoduje uporządkowanie punków tak, że tworzą one przekątną pola biegnącą od prawego dolnego rogu do lewego górnego rogu prostokątnego pola.

Zasób interaktywny dostępny pod adresem https://zpe.gov.pl/a/DwY8eJarE