Algorytm wyszukiwania binarnego z PRZYKŁADEM

Zanim nauczymy się wyszukiwania binarnego, nauczmy się:

Co to jest wyszukiwanie?

Wyszukiwanie to narzędzie umożliwiające użytkownikowi wyszukiwanie dokumentów, plików, multimediów i innych typów 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 typ algorytmu wyszukiwania, który znajduje i pobiera dane z posortowanej listy elementów. Jego podstawowa zasada działania polega na dzieleniu danych na liście na pół, aż do momentu znalezienia i wyświetlenia użytkownikowi wymaganej wartości w wynikach wyszukiwania. Wyszukiwanie binarne jest powszechnie znane jako wyszukiwanie w połowie przedziału lub wyszukiwanie logarytmiczne.

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ż środkowy element, wyszukiwanie analizuje górne wartości do środkowego elementu w celu porównania i dopasowania
• W przypadku, gdy wartość klucza jest większa niż środkowy element, wyszukiwanie analizuje niższe wartości w stosunku do środkowego elementu w celu porównania i dopasowania

Przykładowe wyszukiwanie binarne

Przyjrzyjmy się przykładowi słownika. Jeśli trzeba 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ć wymagane słowo.

Powyższy obraz ilustruje następujące zjawisko:

1. Masz tablicę składającą się z 10 cyfr i należy znaleźć element 59.
2. Wszystkie elementy są oznaczone indeksem od 0 – 9. Teraz obliczany jest środek tablicy. Aby to zrobić, należy podzielić skrajne lewe i prawe wartości indeksu przez 2. Wynik wynosi 4.5, ale my bierzemy wartość dolną. Zatem środek to 4.
3. Algorytm usuwa wszystkie elementy ze środka (4) do najniższej granicy, ponieważ 59 jest większe niż 24, a teraz tablica zawiera tylko 5 elementów.
4. Teraz 59 jest większe niż 45 i mniejsze niż 63. Środek to 7. Stąd prawa wartość indeksu staje się środkiem – 1, co równa się 6, a lewa wartość indeksu pozostaje taka sama jak poprzednio, czyli 5.
5. W tym momencie wiesz, że 59 następuje po 45. Zatem lewy indeks, który wynosi 5, również staje się środkowy.
6. Te iteracje są kontynuowane, dopóki tablica nie zostanie zredukowana do tylko jednego elementu lub znaleziony element nie stanie się środkiem tablicy.

2 przykład

Przyjrzyjmy się poniższemu przykładowi, aby zrozumieć działanie wyszukiwania binarnego

1. Masz tablicę posortowanych wartości od 2 do 20 i musisz zlokalizować 18.
2. Średnia z dolnej i górnej granicy wynosi (l + r) / 2 = 4. Szukana wartość jest większa niż środek, który wynosi 4.
3. Wartości tablicy mniejsze niż średnia są usuwane z wyszukiwania i przeszukiwane są wartości większe niż wartość średnia 4.
4. Jest to powtarzający się proces dzielenia, dopóki nie zostanie znaleziony właściwy element do przeszukania.

Dlaczego potrzebujemy wyszukiwania binarnego?

Poniższe powody sprawiają, że wyszukiwanie binarne jest lepszym wyborem jako algorytm wyszukiwania:

• Wyszukiwanie binarne działa wydajnie na posortowanych danych, niezależnie od rozmiaru danych
• Zamiast przeprowadzać wyszukiwanie poprzez sekwencyjne przeglądanie danych, algorytm binarny losowo uzyskuje dostęp do danych, aby znaleźć wymagany element. Dzięki temu cykle wyszukiwania są krótsze i dokładniejsze.
• Wyszukiwanie binarne porównuje posortowane dane 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 w pozostałej połowie tablicy

Poznaj nasz kolejny samouczek dotyczący Wyszukiwanie liniowe: Python, C++ Przykład

Podsumowanie

• Wyszukiwanie to narzędzie umożliwiające użytkownikowi wyszukiwanie dokumentów, plików i innych typów danych. Wyszukiwanie binarne to zaawansowany typ algorytmu wyszukiwania, który wyszukuje i pobiera dane z posortowanej listy elementów.
• Wyszukiwanie binarne jest powszechnie znane jako wyszukiwanie półprzedziałowe lub wyszukiwanie logarytmiczne
• Działa poprzez podzielenie tablicy na pół przy każdej iteracji znalezionego wymaganego elementu.
• Kolekcja algorytm binarny bierze środek tablicy, dzieląc sumę wartości indeksu z lewej i prawej strony przez 2. Teraz algorytm usuwa 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 w celu znalezienia wymaganego elementu. Dzięki temu cykle wyszukiwania są krótsze i dokładniejsze.
• Wyszukiwanie binarne porównuje posortowane dane w oparciu o zasadę porządkowania, zamiast używać porównań równości, które są powolne i niedokładne.
• Wyszukiwanie binarne nie jest odpowiednie dla nieposortowanych danych.