Algorytm wyszukiwania binarnego: funkcja, korzyści, złożoność czasu i przestrzeni

Wstęp

W każdym systemie obliczeniowym wyszukiwanie jest jedną z najważniejszych funkcji do opracowania. Techniki wyszukiwania są używane podczas pobierania plików, indeksowania i wielu innych aplikacji. Dostępnych jest wiele technik wyszukiwania. Jednym z nich jest technika wyszukiwania binarnego.

Algorytm wyszukiwania binarnego działa na zasadzie pomijania połowy listy w każdej iteracji. Dzieli listę, dopóki nie znajdzie wartości, której szuka na danej liście. Algorytm wyszukiwania binarnego to szybkie uaktualnienie do prostego algorytmu wyszukiwania liniowego.

Nie jest wymagane doświadczenie w kodowaniu. Wsparcie kariery 360°. Dyplom PG z uczenia maszynowego i sztucznej inteligencji z IIIT-B i upGrad.

Działanie algorytmu wyszukiwania binarnego

Pierwszą rzeczą, na którą należy zwrócić uwagę, jest to, że algorytm wyszukiwania binarnego zawsze działa na posortowanej liście. Dlatego pierwszym logicznym krokiem jest posortowanie dostarczonej listy. Po sortowaniu mediana listy jest sprawdzana z żądaną wartością.

• Jeśli żądana wartość jest równa wartości indeksu centralnego, to jako odpowiedź zwracany jest indeks.

• Jeśli wartość docelowa jest niższa niż transakcja indeksu centralnego listy, prawa strona listy jest ignorowana.

• Jeśli żądana wartość jest większa niż wartość wskaźnika centralnego, lewa połowa jest odrzucana.

• Proces jest następnie powtarzany na skróconych listach, aż do znalezienia wartości docelowej.

Przykład 1

Spójrzmy na algorytm na przykładzie. Załóżmy, że istnieje lista z następującymi numerami:

1, 15, 23, 7, 6, 14, 8, 3, 27

Przyjmijmy, że pożądana wartość to 27. Całkowita liczba elementów na liście to 9.

Pierwszym krokiem jest posortowanie listy. Po posortowaniu lista wyglądałaby mniej więcej tak:

1, 3, 6, 7, 8, 14, 15, 23, 27

Ponieważ liczba elementów na liście wynosi dziewięć, centralny indeks wynosiłby pięć. Wartość pod indeksem pięć to 8. Żądana wartość 27 jest porównywana z wartością 8. Najpierw sprawdź, czy wartość jest równa 8, czy nie. Jeśli tak, zwróć indeks i zakończ.

Ponieważ 27 jest większe niż 8, zignorowalibyśmy lewą część i przeszli tylko prawą stronę listy. Nowa lista do przebycia to:

14, 15, 23, 27

Uwaga: W praktyce lista nie jest obcinana. Zawęża się tylko obserwację. Tak więc „nowej listy” nie należy mylić z tworzeniem nowej listy lub skracaniem oryginalnej. Chociaż można by to zaimplementować za pomocą nowej listy, pojawiają się dwa problemy. Po pierwsze, będzie narzut pamięci. Każda nowa lista zwiększy złożoność przestrzeni. Po drugie, oryginalne indeksy muszą być śledzone w każdej iteracji.

Nowy indeks centralny może być traktowany jako drugi lub trzeci element, w zależności od implementacji. Tutaj uznamy trzeci element za centralny. Wartość 23 jest porównywana z wartością 27. Ponieważ wartość jest większa niż wartość środkowa, odrzucimy lewą połowę.

Lista do przebycia to:

27

Ponieważ lista zawiera tylko jeden element, uważa się ją za element centralny. W związku z tym porównujemy żądaną wartość z 27. Gdy się zgadzają, zwracamy wartość indeksu 27 z oryginalnej listy.

Przykład #2

Na tej samej liście załóżmy, że pożądana wartość to 2.

Po pierwsze, środkowa wartość osiem jest porównywana z 2. Ponieważ żądana wartość jest mniejsza niż środkowa, zawężamy naszą uwagę do lewej strony listy.

Nowe przejście będzie się składać z:

1, 3, 6, 7

Weźmy centralny element jako drugi element. Pożądana wartość dwa jest porównywana z 3. Ponieważ wartość jest wciąż mniejsza, ponownie zawężamy obszar zainteresowania do lewej strony listy.

Nowe przejście będzie się składać z:

1

Ponieważ lista przemierzania zawiera tylko jeden element, wartość jest bezpośrednio porównywana z pozostałym elementem. Widzimy, że wartości się nie zgadzają. Dlatego wyrywamy się z pętli z komunikatem o błędzie: wartość nie została znaleziona .

Zaawansowana certyfikacja Data Science, ponad 250 partnerów rekrutacyjnych, ponad 300 godzin nauki, 0% EMI

Złożoność czasu i przestrzeni

Złożoność czasowa algorytmu przeszukiwania binarnego wynosi O(log n). Najlepszym przypadkiem złożoność czasowa byłaby O(1), gdy indeks centralny bezpośrednio pasowałby do pożądanej wartości. Najgorszym scenariuszem mogą być wartości na końcu listy lub wartości, których nie ma na liście.

Złożoność przestrzenna algorytmu wyszukiwania binarnego zależy od implementacji algorytmu. Istnieją dwa sposoby na jego realizację:

1. Metoda iteracyjna
2. Metoda rekurencyjna

Obie metody są takie same, z dwiema różnicami w implementacji. Po pierwsze, w metodzie rekurencyjnej nie ma pętli. Po drugie, zamiast przekazywać nowe wartości do następnej iteracji pętli, przekazuje je do następnej rekurencji. W metodzie iteracyjnej iteracje można kontrolować za pomocą warunków pętli, podczas gdy w metodzie rekurencyjnej jako warunek brzegowy stosuje się maksimum i minimum.

W metodzie iteracyjnej złożoność przestrzeni wynosiłaby O(1). Natomiast w metodzie rekurencyjnej złożoność przestrzeni byłaby O(log n).

Korzyści

• Algorytm wyszukiwania binarnego jest dość prostym algorytmem wyszukiwania do zaimplementowania.

• Jest to znacząca poprawa w stosunku do wyszukiwania liniowego i działa prawie tak samo w porównaniu z niektórymi trudniejszymi do zaimplementowania algorytmami wyszukiwania.

• Algorytm wyszukiwania binarnego dzieli listę na pół przy każdej iteracji, zamiast sekwencyjnie przeczesywać listę. Na dużych listach ta metoda może być naprawdę przydatna.

Zamówienie: Klasyfikacja drzewa decyzyjnego: wszystko, co musisz wiedzieć

Wniosek

Algorytm wyszukiwania binarnego jest szeroko stosowanym algorytmem w dziedzinie obliczeniowej. Jest to gruby i dokładny algorytm wyszukiwania, który może działać dobrze zarówno na dużych, jak i małych zestawach danych. Algorytm wyszukiwania binarnego to prosty i niezawodny algorytm do wdrożenia. Dzięki analizie czasu i przestrzeni korzyści płynące z zastosowania tej konkretnej techniki są oczywiste.

Jeśli jesteś zainteresowany nauką o danych, sprawdź IIIT-B i upGrad's PG Diploma in Data Science, który jest stworzony dla pracujących profesjonalistów i oferuje ponad 10 studiów przypadków i projektów, praktyczne warsztaty praktyczne, mentoring z ekspertami z branży, 1- on-1 z mentorami branżowymi, ponad 400 godzin nauki i pomocy w pracy z najlepszymi firmami.