Wyszukiwanie binarne JavaScript

| | | | | | |

Jak zakodować wyszukiwanie binarne w JavaScript

Algorytmy wyszukiwania znacznie ułatwiają życie programistom. Ułatwia to znalezienie konkretnego elementu w zbiorze danych składającym się z dziesiątek, setek lub tysięcy elementów.

Jedną z najpopularniejszych form wyszukiwania jest wyszukiwanie binarne. To wyszukiwanie szybko odnajduje element w tablicy. Za każdym razem, gdy wyszukiwanie sprawdza element, zmniejsza o połowę liczbę elementów do znalezienia.

W tym przewodniku omówimy, czym są wyszukiwania binarne i jak działają. Następnie przejdziemy do implementacji wyszukiwania binarnego przy użyciu dwóch różnych podejść: iteracyjnego i rekurencyjnego.

Zbudujmy algorytm wyszukiwania binarnego w !

Co to jest wyszukiwanie binarne?

Wyszukiwanie binarne to algorytm komputerowy, który wyszukuje element w uporządkowanej tablicy.

Rozpocznij w środku tablicy i sprawdź, czy środkowy element jest mniejszy, równy lub większy niż szukana liczba.

Jeśli liczba jest mniejsza, algorytm wie, jak szukać w lewej połowie tablicy, gdzie są mniejsze liczby ; jeśli liczba jest większa, algorytm skupi się na prawej połowie tablicy. Wyszukiwanie binarne działa tylko na uporządkowanych listach.

Wyszukiwania binarne są bardziej wydajne niż wyszukiwania liniowe. W rzeczywistości za każdym razem, gdy przeprowadzane jest wyszukiwanie, liczba pozycji pozostałych do znalezienia na liście zmniejsza się o połowę.

Jak korzystać z wyszukiwania binarnego

Wyszukiwanie binarne jest łatwe do zrozumienia, gdy się go nauczysz.

Przed wdrożeniem algorytmu wyszukiwania binarnego przyjrzyjmy się – zrób krok. Na liście znajdziemy cyfrę „9”. Zacznijmy od uporządkowanej listy:

2 6 < / td> 8 9 10

Najpierw musimy znaleźć środkową liczbę i przypisać ją do zmiennej. Można to znaleźć, obliczając sumę pierwszej i ostatniej liczby i dzieląc przez dwa. Nazwiemy tę "centralną" zmienną:

Start < br> Średni
Koniec
2 6 8 9 10

8 to nasza średnia liczba. W ten sposób możemy porównać numer centralny z tym, którego szukamy. Jeśli centralna liczba jest taka sama jak ta, której szukamy, nasze wyszukiwanie może się zatrzymać.

W tym przykładzie 8 nie równa się 9. Nasze poszukiwania są kontynuowane.

Musimy więc porównać, czy liczba w środku jest większa niż 9. Tak nie jest.

To mówi nam, że szukana liczba musi znajdować się po środkowej liczby. 9 jest większe niż 8 na uporządkowanej liście. ustaw nasz numer początkowy tak, aby był równy liczbie środkowej. Dzieje się tak, ponieważ wiemy, że szukana liczba nie występuje przed liczbą środkową.

Jeśli szukana przez nas liczba jest większa, ustawimy ostateczną liczbę tak, aby była równa środkowej liczbie. Ponieważ liczba jest mniejsza niż środkowa liczba, możemy skoncentrować nasze poszukiwania na dolnej połowie listy.

Wyszukiwanie binarne powtarza się ponownie w górnej połowie listy, ponieważ 9 jest większe niż 8:

< td> Średni


Start Koniec
2 6 8 < /td> 9 10

Znajdźmy numer centralny. To 9. Możemy porównać 9 z liczbą, której szukamy. 9 to liczba, której szukamy.

Oznacza to, że nasze badania mogą się zatrzymać. Udało nam się znaleźć numer 9 na naszej liście!

Jak zaimplementować wyszukiwanie binarne w JavaScript

Wyszukiwania binarne można zaimplementować przy użyciu podejścia iteracyjnego lub rekurencyjnego.

Iteracyjne wyszukiwanie binarne

Iteracyjne wyszukiwanie binarne wykorzystuje pętlę while do znalezienia elementu na liście. Ta pętla będzie działać, dopóki element nie zostanie znaleziony na liście lub dopóki lista nie zostanie przeszukana.

Zacznijmy od napisania funkcji funkcja wykonująca nasze wyszukiwanie binarne:

Zacznijmy od zdefiniowania dwóch zmiennych: start i end. Śledzą one najwyższe i najniższe wartości, z którymi pracują nasze badania. Używamy pętli while , która działa do momentu, gdy numer początkowy jest większy niż numer końcowy. Ta pętla oblicza liczbę pośrednią między początkiem a końcem listy.

Jeśli szukana liczba jest równa liczbie w środku, liczba w środku jest zwracana do naszego głównego programu. liczba jest mniejsza, wartość inicjatora jest równa środkowej liczbie plus 1. Porównań tych dokonuje się za pomocą instrukcji if .

W przeciwnym razie ostateczna liczba jest ustawiana jako liczba środkowa minus 1. Jeśli nasza liczba nie zostanie znaleziona po wykonaniu pętli while, zwraca ona -1. Nazywamy to warunkiem podstawowym.W naszym programie głównym sprawdzi, czy zwrócona liczba jest równa -1. oznacza to, że nasz numer nie został znaleziony.

Nasza funkcja jeszcze nie działa. Musimy napisać główny program, aby go nazwać:

Zdefiniowaliśmy listę numerów do wyszukania oraz numer, który chcemy znaleźć na naszej liście. Następnie wywołaliśmy funkcję binarySearch. To zrobi nasze badania. Wyszukiwanie zwróci -1 lub pozycję szukanego elementu.

-1 oznacza, że nie można znaleźć elementu. Jeśli element nie zostanie znaleziony, wykonywana jest zawartość naszej instrukcji else . W przeciwnym razie wykonywana jest zawartość instrukcji if .

Uruchommy nasz kod:

To mówi nam, że nasze wyszukiwanie się powiodło!

Rekursywne wyszukiwanie binarne

Rekurencyjne wyszukiwanie binarne jest uważane za bardziej eleganckie niż wyszukiwanie iteracyjne. Dzieje się tak, ponieważ wyszukiwania binarne wykonują tę samą operację w kółko na liście. To zachowanie można zaimplementować za pomocą algorytmu rekurencji.

Otwórz nowy plik JavaScript i wklej ten kod:

Ten kod wykonuje te same porównania, co nasze pierwsze wyszukiwanie. Sprawdź, czy środkowa liczba jest równa, większa lub mniejsza od liczby, której szukamy.

Na początku naszego funkcja , użyliśmy instrukcji if, aby sprawdzić, czy numer początkowy jest większy niż numer końcowy. Jeśli tak, oznacza to, że nasz element nie został znaleziony na podanej przez nas liście. W tym przypadku zwracamy -1 do programu głównego.

Jeśli szukany numer jest taki sam jak numer centralny, numer centralny jest zwracany do programu głównego. szukana liczba jest większa lub mniejsza niż liczba centralna, nasza funkcja wyszukiwania binarnego jest wykonywana ponownie.To trwa do momentu znalezienia naszego elementu.

Aby wykonać tę funkcję, będziemy musieli dokonaj modyfikacji w naszym głównym programie:

Musimy przekazać jeszcze dwa parametry: wartości „start” i „koniec”. Wartość „start” jest równa 0. Wartość „end” jest równa długości listy minus jeden.

Uruchommy nasz kod i zobaczmy, co się stanie:

Nasze wyszukiwanie binarne powiodło się! Wykorzystuje ten sam podstawowy algorytm, co podejście iteracyjne. Różnica polega na tym, że wyszukiwanie binarne jest wykonywane przy użyciu funkcji wywoływanej do momentu znalezienia elementu lub do zakończenia wyszukiwania na liście, w zależności od tego, co nastąpi wcześniej.

Wnioski

Wyszukiwanie binarne ułatwia znalezienie pozycji na liście. Za każdym razem, gdy przeprowadzane jest wyszukiwanie, liczba elementów pozostałych do znalezienia na liście zmniejsza się o połowę. Dzięki temu wyszukiwanie binarne jest bardziej wydajne niż wyszukiwanie liniowe.

Jesteś teraz gotowy do zaimplementuj wyszukiwanie binarne w JavaScript jak ekspert!