Przy opracowywaniu algorytmów rozwiązywania wielu problemów często pojawia się problem realizacji wyszukiwania określonej grupy danych według określonych kryteriów. Podczas eksploracji uporządkowanej lub nieuporządkowanej sekwencji wyszukiwanie można przeprowadzić różnymi metodami. W ogólnym przypadku do rozwiązania problemu wyszukiwania brana jest pod uwagę pewna tablica danych, w której wymagane jest znalezienie danego elementu.
Instrukcje
Krok 1
Najłatwiejszym sposobem znalezienia znanego elementu w tablicy danych jest iteracja po jego wartościach. Algorytm ten jest optymalny dla małych ilości informacji. Jego istota polega na przejściu znanej sekwencji danych (tablicy) i porównaniu każdego elementu z pożądaną wartością. W przypadku znalezienia dopasowania, w zależności od określonych kryteriów, wyszukiwanie można zakończyć lub kontynuować do końca tablicy.
Krok 2
Jednak pomimo prostoty implementacji tej metody jej zastosowanie jest niepożądane w tablicach zawierających duże ilości informacji, gdyż znacznie zwiększa to zasobochłonność algorytmu. Aby zoptymalizować wyszukiwanie w tym przypadku, lepiej wstępnie posortować wartości w tablicy i zaimplementować algorytmy wyszukiwania: po drzewie binarnym, po drzewie Fibonacciego, metodą ekstrapolacji.
Krok 3
Pracując z uporządkowaną tablicą, użyj bardziej wydajnego algorytmu - metody wyszukiwania binarnego. Jej istota polega na tym, że w procesie wyliczania granice przedziału zbliżają się do siebie, zawężając tym samym obszar poszukiwań. Porównaj szukaną wartość z ponumerowanym elementem tablicy. Jeśli próbka pasuje do elementu, problem uznaje się za rozwiązany. Jeśli żądany element jest większy niż środkowy element, dalsze wyszukiwanie należy przeprowadzić w części tablicy znajdującej się na prawo od środkowego elementu (od początku tablicy do środkowego elementu-1). Jeśli wyszukiwanie jest mniejsze niż środkowy element, wyszukiwanie jest kontynuowane w części tablicy od środkowego do ostatniego elementu. Po ustaleniu nowego obszaru wyszukiwania, opisany algorytm jest powtarzany, identyfikując dopasowania lub zawężając obszar przetwarzania. Ten schemat jest poprawny dla tablicy malejącej.
Krok 4
Poszczególne problemy znalezienia minimalnego lub maksymalnego elementu w danej sekwencji rozwiązuje się przez przypisanie początkowego elementu jako pożądanego. Następnie wykonywane jest sekwencyjne wyliczanie pozostałych wartości tablicy: druga z pierwszą, trzecia z pierwszą itd. Porównując wartość przyjmowaną jako standard, staje się jasne, czy w tablicy znajduje się element, który jest bardziej zgodny z danym warunkiem (minimum lub maksimum). Gdy zostanie znaleziony, jest już traktowany jako standard, a wyliczanie jest kontynuowane od bieżącej pozycji do końca tablicy. W efekcie minimalną (lub maksymalną) wartością w tej grupie jest element, który został ostatnio uznany za standard.
