Wyszukiwanie binarne a wyszukiwanie liniowe
Wyszukiwanie liniowe, znane również jako przeszukiwanie sekwencyjne, jest najprostszym algorytmem wyszukiwania. Wyszukuje określoną wartość na liście, sprawdzając każdy element na liście. Wyszukiwanie binarne jest również metodą używaną 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 do zlokalizowania danej pozycji na liście.
Co to jest wyszukiwanie liniowe?
Wyszukiwanie liniowe to najprostsza metoda wyszukiwania, która sprawdza każdy element na liście sekwencyjnie, aż znajdzie określony element. Dane wejściowe w metodzie wyszukiwania liniowego to sekwencja (na przykład tablica, kolekcja lub ciąg znaków) oraz element, który należy przeszukać. Dane wyjściowe mają wartość true, jeśli określony element znajduje się w podanej sekwencji lub false, jeśli nie ma go w sekwencji. Ponieważ ta metoda sprawdza każdą pozycję na liście, aż do znalezienia określonej pozycji, w najgorszym przypadku przejdzie przez wszystkie elementy na liście, zanim znajdzie wymagany element. Złożoność wyszukiwania liniowego wynosi o (n). Dlatego uważa się, że jest on zbyt wolny do wyszukiwania elementów na dużych listach. Ale to jest bardzo proste i łatwiejsze do wdrożenia.
Co to jest wyszukiwanie binarne?
Wyszukiwanie binarne jest również metodą używaną 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ż środkowy element, metoda rozpoczyna ponownie, używając tylko dolnej połowy posortowanej listy. Jeśli przeszukiwany element jest mniejszy niż środkowy element, metoda rozpoczyna ponownie, używając tylko górnej połowy posortowanej listy. Jeśli szukanego elementu nie ma 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 konsekwencji,wyszukiwanie binarne działa w czasie logarytmicznym, co daje średnią wydajność o (log n) przypadku.
Jaka jest różnica między wyszukiwaniem binarnym a wyszukiwaniem liniowym?
Mimo że zarówno wyszukiwanie liniowe, jak i wyszukiwanie binarne są metodami wyszukiwania, istnieje kilka różnic. Podczas gdy wyszukiwanie binarne działa na listach posortowanych, wyszukiwanie liniowe może również działać na listach niesortowanych. Sortowanie listy ma zazwyczaj średnią złożoność przypadku 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 stosować z dużymi listami ze względu na średnią wydajność przypadków wynoszącą (n). Z drugiej strony, wyszukiwanie binarne jest uważane za bardziej wydajną metodę, której można używać w przypadku dużych list. Jednak wdrożenie wyszukiwania binarnego może być dość skomplikowane, a badanie wykazało, że dokładny kod wyszukiwania binarnego można znaleźć tylko w pięciu z dwudziestu książek.
