Wyszukiwanie binarne w Python
Wyszukiwanie binarne jest sposobem na znalezienie określonego elementu na liście. Wyobraźmy sobie, że mamy listę dziesięciu tysięcy elementów i musimy znaleźć pozycję indeksu jednego wpisu. Możemy szybko znaleźć lokalizację indeksu elementu za pomocą techniki wyszukiwania binarnego. Istnieją inne algorytmy wyszukiwania, ale najdłuższym zastosowanym jest wyszukiwanie binarne. Najpierw sortuj obiekty, jeśli jeszcze nie zostały posortowane.
Do znalezienia pozycji elementu można zastosować podejścia rekurencyjne i iteracyjne algorytmu. Strategia rekurencyjna jest stosowana po podejściu do podziału i podboju. W ten sposób funkcja jest wykonywana, dopóki nie znajdzie elementu na liście. Aby odkryć lokalizację indeksu elementu, technika iteracyjna wielokrotnie powtarza zestaw słów. Ten proces odbywa się za pomocą pętli While. Ponieważ nie musimy wyszukiwać każdego indeksu listy, wyszukiwanie binarne jest bardziej wydajne niż wyszukiwanie liniowe.
Zacznijmy od podstawowego zrozumienia wyszukiwania binarnego.
Przykład 1:
Najpierw stosujemy podejście iteracyjne do wdrożenia wyszukiwania binarnego. Przejdziemy się przez listę, powtarzając sekwencję stwierdzeń. Będziemy nadal szukać wartości środkowej, dopóki jej nie znajdziemy.
To jest wdrożenie Pythona iteracyjnego podejścia do funkcji wyszukiwania binarnego. Jeśli „Search_num” jest obecny na podanej liście, zwraca jedną; W przeciwnym razie daje -1. W tym programie skonstruowaliśmy funkcję Binary Search (), która akceptuje dwa argumenty: lista do sortowania i numer do wyszukiwania. Skonfigurowaliśmy dwie zmienne, aby śledzić najniższe i największe wartości listy. Niska ma wartość początkową 0, wysoka ma wartość LEN (List1) - 1, a środek ma wartość 0. Pętla While jest następnie zapisywana z ograniczeniem, że najniższa równa się i jest mniejsza niż najwyższa. Pętla While itera się, jeśli liczba jeszcze nie została znaleziona. Punkt środkowy znajduje się w pętli While. Następnie dopasowujemy wartość indeksu do liczby, której szukaliśmy. Jeśli wartość średniego indeksu jest mniejsza niż „wyszukiwanie numeru”, przypisujemy ją i podnosimy wartość indeksu. Skupienie się na zmianie wyszukiwania po lewej stronie. Ustaw wartość środkową na maksimum, jeśli jest wysoka. Zwrócić w połowie, jeśli „Search_num” jest równe wartości średniej. Będzie to trwało, aż niskie i wysokie będą równe, a niski jest mniejszy niż wysoki. Jeśli dojdziemy do końca funkcji, wiemy, że element nie ma na liście. Do funkcji wywołującej zwracamy -1.
def binary_search (jeden, Search_num):niski = 0
Wysoki = len (jeden) - 1
Mid = 0
podczas gdy niski <= high:
mid = (wysoki + niski) // 2
Jeśli jeden [środkowy] Search_num:
Wysokie = połowa - 1
w przeciwnym razie:
powrót w połowie
zwrot -1
jeden = [19, 23, 43, 56, 65, 71, 80]
Search_num = 43
wyjście = binary_search (jeden, Search_num)
Jeśli wyjście != -1:
print („element jest na indeksie”, str (wyjściowy))
w przeciwnym razie:
druk („element nie jest dostępny na liście”)
Tutaj możesz zobaczyć, że wymagana liczba znajduje się w pozycji indeksu 2.
Przykład 2:
Spójrzmy na rekurencyjne podejście do wyszukiwania binarnego. Podejście rekurencji można zastosować w wyszukiwaniu binarnym. Wykonamy funkcję rekurencyjną, która wywołuje się do momentu spełnienia warunku. Poprzedni program jest podobny do tego przed nim. Zadeklarowano funkcję rekurencyjną, a także jej stan podstawowy. Obliczamy średnią liczbę, tak jak w poprzednim programie. Aby kontynuować wyszukiwanie binarne, użyliśmy instrukcji IF. Zostanie zwrócony, jeśli wartość średnia jest równoważna z liczbą, której szukamy. Jeśli wartość średnia jest poniżej wartości, zwiększamy ją o jedną i przypisujemy do niskiej za pomocą naszej funkcji rekursive binary search (). Napisaliśmy nasz główny program w ostatniej sekcji. Procedura Binary Search () wymaga teraz 2 parametrów, co jest jedyną modyfikacją z poprzedniego programu. Niezdolność funkcji rekurencyjnej do przypisywania wartości początkowych do niskiego, wysokiego i środkowego jest przyczyną tego. Wartość tych zmiennych będzie resetować za każdym razem, gdy wywoływa się rekurencja.
def binary_search (jeden, niski, high, search_num):Jeśli Low Search_num:
return binary_search (jeden, niski, połowa - 1, search_num)
w przeciwnym razie:
return binary_search (jeden, połowa + 1, high, search_num)
w przeciwnym razie:
zwrot -1
jeden = [19, 23, 43, 56, 65, 71, 80]
Search_num = 65
wyjście = binary_search (jeden, 0, len (jeden) -1, Search_num)
Jeśli Search_num != -1:
print („element jest na indeksie”, str (wyjściowy))
w przeciwnym razie:
druk („element nie jest dostępny na liście”)
Wymagana wartość znajduje się w indeksie 4, jak widać na poniższym obrazie.
Przykład 3:
Kolejny przykład techniki wyszukiwania binarnego, powszechnie znanego jako algorytm wyszukiwania w połowie interval, służy do zlokalizowania wartości docelowej w ramach posortowanej tablicy. Ten program zwraca true, jeśli liczba znajduje się na liście.
def binary_search (my_list, search_num):jeden = 0
finał = len (my_list) -1
znalezione = fałsz
While (jeden<=final and not found):
mid = (jeden + final) // 2
Jeśli my_list [mid] == Search_num:
znalezione = prawda
w przeciwnym razie:
Jeśli Search_num
w przeciwnym razie:
jeden = połowa + 1
Znaleziono powrót
druk (binary_search ([1,2,3,4,5], 3))
Drukuj (binary_search ([11,22,33,44,55], 5))
Poniżej znajduje się wyjście.
Wniosek:
Najskuteczniejszym i szybkim podejściem do wyszukiwania wpisu na liście jest użycie algorytmu wyszukiwania binarnego. Przeskakuje bezsensowną analogię. Jak sama nazwa mówi, wyszukiwanie jest podzielone na dwa kawałki. Koncentruje się na boku listy najbliżej liczby, której szukamy. W najlepszej sytuacji złożoność algorytmu wyszukiwania binarnego wynosi O (1). Dzieje się tak, gdy element, którego szukamy, pojawia się w pierwszym porównaniu. Najgorsza i średnia złożoność przypadku wyszukiwania binarnego to O (logn). Całkowita liczba wyszukiwań wymaganych do zlokalizowania elementu określa to. Omówiono różne podejścia do określania pozycji indeksu danej liczby.