Różnica między wyszukiwaniem binarnym a wyszukiwaniem liniowym

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 także metoda zlokalizowania 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 jest najprostszą metodą wyszukiwania, która sprawdza kolejno 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 ciąg) i element, który należy przeszukać. Dane wyjściowe są prawdziwe, 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, aż do znalezienia określonego elementu, 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 zbyt wolny, aby można go było stosować 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 także metoda zlokalizowania 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, ponownie uruchamia metodę, używając tylko dolnej połowy posortowanej listy. Jeśli szukany element jest mniejszy niż środkowy element, ponownie uruchamia metodę, 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 związku z tym wyszukiwanie binarne przebiega w czasie logarytmicznym, co powoduje średnią wydajność o (log n).

Jaka jest różnica między wyszukiwaniem binarnym a wyszukiwaniem liniowym?

Mimo że wyszukiwanie liniowe i binarne są metodami wyszukiwania, mają one kilka różnic. Podczas gdy wyszukiwanie binarne działa na posortowanych listach, wyszukiwanie liniowe może również działać na nieposortowanych listach. Sortowanie listy zazwyczaj ma średnią złożoność wielkości liter n log n. wyszukiwanie liniowe jest proste i łatwe do wdrożenia niż wyszukiwanie binarne. Jednak wyszukiwanie liniowe jest zbyt wolne, aby można go było stosować z dużymi listami ze względu na jego średnią (o) wydajność. Z drugiej strony wyszukiwanie binarne jest uważane za bardziej wydajną metodę, której można by używać z dużymi listami. Ale 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.