I_R_W14_M23_C++ Jak szybko znaleźć dane? Wyszukiwanie liniowe vs binarne
W tym e‑materiale powtarzamy wiadomości ze szkoły podstawowej.
Zastanów się, jak często (nawet nieświadomie!) wykorzystujesz w codziennym życiu algorytmy wyszukiwania określonego elementu. Najczęściej korzystasz z konkretnych kryteriów – szukasz butów w danym rozmiarze czy książek konkretnej autorki. To samo zadanie wykonują ze ciebie wyszukiwarki internetowe, choć one korzystają z innych algorytmów.
Wyszukiwanie danych to jedno z podstawowych zagadnień informatyki, z którym spotykamy się zarówno w prostych programach, jak i w zaawansowanych systemach komputerowych. W materiale przedstawiono dwie popularne metody wyszukiwania: liniową oraz binarną. Pierwsza z nich polega na sprawdzaniu elementów po kolei, natomiast druga wykorzystuje uporządkowanie danych, aby znacząco przyspieszyć odnajdywanie informacji. Porównanie tych metod pozwala lepiej zrozumieć, jak dobór algorytmu wpływa na wydajność programu.
Ćwiczenie na rozgrzewkę:
Poznasz metodę wyszukiwania liniowego.
Zapoznasz się z iteracyjną oraz rekurencyjną wersją algorytmu wyszukiwania binarnego.
Wyjaśnisz, czym są lider oraz idol.
Przeanalizujesz algorytmy wyboru lidera oraz wyszukiwania idola w zbiorze.
Rozwiążesz zadania wymagające wykorzystania algorytmów wyszukiwania określonego elementu w zbiorze.