Program w języku Python do wyszukiwania binarnego (rekursywny i iteracyjny)
Krótko mówiąc, ten algorytm wyszukiwania wykorzystuje zbiór elementów, który jest już posortowany, ignorując połowę elementów już po jednym porównaniu.
- Porównaj x ze środkowym elementem.
- Jeśli x pasuje do środkowego elementu, zwracamy środkowy indeks.
- W przeciwnym razie, jeśli x jest większe niż element środkowy, wówczas x może leżeć tylko w prawej (większej) połowie podtablicy za elementem środkowym. Następnie ponownie stosujemy algorytm dla prawej połowy.
- W przeciwnym razie, jeśli x jest mniejsze, docelowy x musi znajdować się w lewej (dolnej) połowie. Stosujemy więc algorytm dla lewej połowy.
Program w języku Python do wyszukiwania binarnego przy użyciu rekurencji
Python3
# Python 3 program for recursive binary search.> # Modifications needed for the older Python 2 are found in comments.> # Returns index of x in arr if present, else -1> def> binary_search(arr, low, high, x):> > # Check base case> > if> high>> => low:> > mid> => (high> +> low)> /> /> 2> > # If element is present at the middle itself> > if> arr[mid]> => => x:> > return> mid> > # If element is smaller than mid, then it can only> > # be present in left subarray> > elif> arr[mid]>x:> > return> binary_search(arr, low, mid> -> 1> , x)> > # Else the element can only be present in right subarray> > else> :> > return> binary_search(arr, mid> +> 1> , high, x)> > else> :> > # Element is not present in the array> > return> -> 1> # Test array> arr> => [> 2> ,> 3> ,> 4> ,> 10> ,> 40> ]> x> => 10> # Function call> result> => binary_search(arr,> 0> ,> len> (arr)> -> 1> , x)> if> result !> => -> 1> :> > print> (> 'Element is present at index'> ,> str> (result))> else> :> > print> (> 'Element is not present in array'> )> |
Wyjście
Element is present at index 3
Złożoność czasu : O(log n)
Przestrzeń pomocnicza : O(logn) [UWAGA: Rekursja tworzy stos wywołań]
Program w języku Python do wyszukiwania binarnego przy użyciu iteracji
Python3
# Iterative Binary Search Function> # It returns index of x in given array arr if present,> # else returns -1> def> binary_search(arr, x):> > low> => 0> > high> => len> (arr)> -> 1> > mid> => 0> > while> low <> => high:> > mid> => (high> +> low)> /> /> 2> > # If x is greater, ignore left half> > if> arr[mid] low = mid + 1 # If x is smaller, ignore right half elif arr[mid]>x: high = mid - 1 # oznacza, że x jest obecny w środku else: return mid # Jeśli dotrzemy tutaj, oznacza to, że elementu nie było return -1 # Tablica testowa arr = [ 2, 3, 4, 10, 40 ] x = 10 # Wynik wywołania funkcji = binary_search(arr, x) if wynik != -1: print('Element występuje w indeksie', str(result)) else: print('Element nie występuje w tablicy ')> |
Wyjście
Element is present at index 3
Złożoność czasu : O(log n)
Przestrzeń pomocnicza : O(1)
Program w Pythonie do wyszukiwania binarnego Korzystanie z wbudowanego modułu bisect
Podejście krok po kroku:
- Kod importuje moduł bisect, który zapewnia obsługę wyszukiwania binarnego.
- Zdefiniowano funkcję binary_search_bisect(), która jako dane wejściowe pobiera tablicę arr i element do przeszukania x.
- Funkcja wywołuje funkcję bisect_left() modułu bisect, która znajduje pozycję elementu w posortowanej tablicy arr, w którym należy wstawić x, aby zachować porządek posortowania. Jeśli element jest już obecny w tablicy, funkcja ta zwróci jego położenie.
- Następnie funkcja sprawdza, czy zwrócony indeks i mieści się w zakresie tablicy i czy element pod tym indeksem jest równy x.
- Jeśli warunek jest spełniony, funkcja zwraca indeks i jako pozycję elementu w tablicy.
- Jeśli warunek jest fałszywy, funkcja zwraca -1, co oznacza, że elementu nie ma w tablicy.
- Następnie kod definiuje tablicę arr i element x do przeszukania.
- Funkcja binary_search_bisect() jest wywoływana z danymi wejściowymi arr i x, a zwrócony wynik jest zapisywany w zmiennej wynikowej.
- Następnie kod sprawdza, czy wynik nie jest równy -1, wskazując, że element znajduje się w tablicy. Jeśli ma wartość true, drukuje pozycję elementu w tablicy.
- Jeśli wynik jest równy -1, to kod wypisuje komunikat, że elementu nie ma w tablicy.
Python3
import> bisect> > def> binary_search_bisect(arr, x):> > i> => bisect.bisect_left(arr, x)> > if> i !> => len> (arr)> and> arr[i]> => => x:> > return> i> > else> :> > return> -> 1> > > # Test array> arr> => [> 2> ,> 3> ,> 4> ,> 10> ,> 40> ]> x> => 10> > # Function call> result> => binary_search_bisect(arr, x)> > if> result !> => -> 1> :> > print> (> 'Element is present at index'> ,> str> (result))> else> :> > print> (> 'Element is not present in array'> )> |
Wyjście
Element is present at index 3
Złożoność czasu : O(log n)
Przestrzeń pomocnicza : O(1)
