Zanim nauczymy się wyszukiwania binarnego, nauczmy się:
Co to jest wyszukiwarka?
Wyszukiwanie to narzędzie, które umożliwia użytkownikowi znajdowanie dokumentów, plików, multimediów lub dowolnego innego rodzaju danych przechowywanych w bazie danych. Wyszukiwanie działa na prostej zasadzie dopasowywania kryteriów do rekordów i wyświetlania ich użytkownikowi. W ten sposób działa najbardziej podstawowa funkcja wyszukiwania.
Co to jest wyszukiwanie binarne?
Wyszukiwanie binarne to zaawansowany algorytm wyszukiwania, który znajduje i pobiera dane z posortowanej listy elementów. Jego podstawowa zasada działania polega na podzieleniu danych na liście na połowę, aż żądana wartość zostanie zlokalizowana i wyświetlona użytkownikowi w wynikach wyszukiwania. Wyszukiwanie binarne jest powszechnie znane jako przeszukiwanie półokresowe lub wyszukiwanie logarytmiczne .
W tym samouczku dotyczącym algorytmu dowiesz się:
- Co to jest wyszukiwarka?
- Co to jest wyszukiwanie binarne?
- Jak działa wyszukiwanie binarne?
- Przykładowe wyszukiwanie binarne
- Dlaczego potrzebujemy wyszukiwania binarnego?
Jak działa wyszukiwanie binarne?
Wyszukiwanie binarne działa w następujący sposób:
- Proces wyszukiwania rozpoczyna się od zlokalizowania środkowego elementu posortowanej tablicy danych
- Następnie wartość klucza jest porównywana z elementem
- Jeśli wartość klucza jest mniejsza niż element środkowy, wyszukiwanie analizuje górne wartości do elementu środkowego w celu porównania i dopasowania
- W przypadku, gdy wartość klucza jest większa niż środkowy element, przeszukiwanie analizuje niższe wartości do środkowego elementu w celu porównania i dopasowania
Przykładowe wyszukiwanie binarne
Spójrzmy na przykład słownika. Jeśli chcesz znaleźć określone słowo, nikt nie przechodzi przez każde słowo w sposób sekwencyjny, ale losowo lokalizuje najbliższe słowa, aby wyszukać żądane słowo.
Powyższy obraz ilustruje:
- Masz tablicę 10 cyfr, a element 59 musi zostać znaleziony.
- Wszystkie elementy są oznaczone indeksem od 0 do 9. Teraz obliczany jest środek tablicy. Aby to zrobić, bierzesz wartości indeksu z lewej i prawej strony i dzielisz je przez 2. Wynik to 4,5, ale bierzemy wartość minimalną. Stąd środek to 4.
- Algorytm opuszcza wszystkie elementy ze środka (4) do najniższego ograniczenia, ponieważ 59 jest większe niż 24, a teraz w tablicy pozostaje tylko 5 elementów.
- Teraz 59 jest większe niż 45 i mniejsze niż 63. Środek to 7. Stąd wartość indeksu po prawej stronie staje się środkowa - 1, co równa się 6, a wartość indeksu po lewej pozostaje taka sama jak poprzednio, czyli 5.
- W tym momencie wiesz, że 59 występuje po 45. W związku z tym lewy wskaźnik, który wynosi 5, również staje się środkiem.
- Te iteracje są kontynuowane, aż tablica zostanie zredukowana tylko do jednego elementu lub znaleziony element stanie się środkiem tablicy.
Przykład 2
Spójrzmy na poniższy przykład, aby zrozumieć działanie wyszukiwania binarnego
- Masz tablicę posortowanych wartości od 2 do 20 i musisz znaleźć 18.
- Średnia dolnej i górnej granicy wynosi (l + r) / 2 = 4. Szukana wartość jest większa niż średnia, która wynosi 4.
- Wartości tablicy mniejsze niż mid są usuwane z wyszukiwania, a przeszukiwane są wartości większe niż mid-value 4.
- Jest to powtarzający się proces dzielenia, dopóki nie zostanie znaleziony przedmiot do przeszukania.
Dlaczego potrzebujemy wyszukiwania binarnego?
Następujące powody sprawiają, że wyszukiwanie binarne jest lepszym wyborem do wykorzystania jako algorytm wyszukiwania:
- Wyszukiwanie binarne działa wydajnie na posortowanych danych bez względu na ich rozmiar
- Zamiast przeszukiwać dane w sekwencji, algorytm binarny uzyskuje dostęp do danych w sposób losowy w celu znalezienia wymaganego elementu. To sprawia, że cykle wyszukiwania są krótsze i dokładniejsze.
- Wyszukiwanie binarne przeprowadza porównania posortowanych danych w oparciu o zasadę porządkowania niż przy użyciu porównań równości, które są wolniejsze i przeważnie niedokładne.
- Po każdym cyklu wyszukiwania algorytm dzieli rozmiar tablicy na połowę stąd w kolejnej iteracji będzie działał tylko na pozostałej połowie tablicy
Podsumowanie
- Wyszukiwanie to narzędzie, które umożliwia użytkownikowi wyszukiwanie dokumentów, plików i innych typów danych. Wyszukiwanie binarne to zaawansowany algorytm wyszukiwania, który znajduje i pobiera dane z posortowanej listy elementów.
- Wyszukiwanie binarne jest powszechnie znane jako przeszukiwanie półokresowe lub wyszukiwanie logarytmiczne
- Działa poprzez podzielenie tablicy na pół przy każdej iteracji pod wymaganym elementem.
- Algorytm binarny zajmuje środek tablicy, dzieląc sumę wartości indeksu z lewej i prawej strony przez 2. Teraz algorytm opuszcza dolną lub górną granicę elementów ze środka tablicy, w zależności od elementu, który ma zostać znaleziony .
- Algorytm losowo uzyskuje dostęp do danych, aby znaleźć wymagany element. To sprawia, że cykle wyszukiwania są krótsze i dokładniejsze.
- Wyszukiwanie binarne przeprowadza porównania posortowanych danych w oparciu o zasadę porządkowania, a nie w przypadku porównań równości, które są powolne i niedokładne.
- Wyszukiwanie binarne nie jest odpowiednie dla danych nieposortowanych.