Wyszukiwanie binarne a wyszukiwanie liniowe
Wyszukiwanie liniowe, znane również jako wyszukiwanie sekwencyjne, jest najprostszym algorytmem wyszukiwania. Wyszukuje określoną wartość na liście, sprawdzając każdy element na liście. Wyszukiwanie binarne to również metoda używana do lokalizowania określonej wartości na posortowanej liście. Metoda wyszukiwania binarnego zmniejsza o połowę liczbę sprawdzanych elementów (w każdej iteracji), skracając czas potrzebny na zlokalizowanie danego elementu na liście.
Co to jest wyszukiwanie liniowe?
Wyszukiwanie liniowe to najprostsza metoda wyszukiwania, która sekwencyjnie sprawdza każdy element na liście, aż znajdzie określony element. Dane wejściowe do metody wyszukiwania liniowego to sekwencja (taka jak tablica, kolekcja lub łańcuch) oraz element, który należy przeszukać. Dane wyjściowe to prawda, jeśli określony element znajduje się w podanej sekwencji, lub fałsz, jeśli nie ma go w sekwencji. Ponieważ ta metoda sprawdza każdy element na liście, dopóki określony element nie zostanie znaleziony, w najgorszym przypadku przejdzie przez wszystkie elementy na liście, zanim znajdzie wymagany element. Złożoność wyszukiwania liniowego jest o(n). Dlatego uważa się, że jest zbyt wolny, aby można go było używać podczas wyszukiwania elementów na dużych listach. Ale jest to bardzo proste i łatwiejsze do wdrożenia.
Co to jest wyszukiwanie binarne?
Wyszukiwanie binarne to również metoda używana do lokalizowania określonego elementu na posortowanej liście. Ta metoda rozpoczyna się od porównania szukanego elementu z elementami na środku listy. Jeśli porównanie ustali, że dwa elementy są równe, metoda zatrzymuje się i zwraca pozycję elementu. Jeśli szukany element jest większy niż element środkowy, ponownie uruchamia metodę, używając tylko dolnej połowy posortowanej listy. Jeśli szukany element jest mniejszy niż element środkowy, ponownie uruchamia metodę, używając tylko górnej połowy posortowanej listy. Jeśli poszukiwany element nie znajduje się na liście, metoda zwróci unikalną wartość wskazującą na to. Dlatego metoda wyszukiwania binarnego zmniejsza o połowę liczbę porównywanych elementów (w każdej iteracji), w zależności od wyniku porównania. W związku z tym wyszukiwanie binarne działa w czasie logarytmicznym, co skutkuje średnią wydajnością obserwacji o(log n).
Jaka jest różnica między wyszukiwaniem binarnym a wyszukiwaniem liniowym?
Mimo że zarówno wyszukiwanie liniowe, jak i wyszukiwanie binarne są metodami wyszukiwania, mają one kilka różnic. Podczas gdy wyszukiwanie binarne działa na listach posortowanych, wyszukiwanie liniowe może działać również na listach nieposortowanych. Sortowanie listy ma na ogół średnią złożoność obserwacji n log n. wyszukiwanie liniowe jest proste i łatwe do zaimplementowania niż wyszukiwanie binarne. Jednak wyszukiwanie liniowe jest zbyt wolne, aby można je było używać z dużymi listami ze względu na jego średnią wydajność w przypadku (o(n)). Z drugiej strony, wyszukiwanie binarne jest uważane za bardziej wydajną metodę, której można używać z dużymi listami. Jednak wdrożenie wyszukiwania binarnego może być dość trudne, a badanie wykazało, że dokładny kod wyszukiwania binarnego można znaleźć tylko w pięciu z dwudziestu książek.
