Program Python pre binárne vyhľadávanie (rekurzívne a iteratívne)
Stručne povedané, tento vyhľadávací algoritmus využíva kolekciu prvkov, ktoré sú už zoradené tak, že polovicu prvkov ignorujú už po jednom porovnaní.
- Porovnajte x so stredným prvkom.
- Ak sa x zhoduje so stredným prvkom, vrátime stredný index.
- V opačnom prípade, ak je x väčšie ako stredný prvok, potom x môže ležať iba v pravom (väčšom) polovičnom podpole za stredným prvkom. Potom znova použijeme algoritmus pre pravú polovicu.
- V opačnom prípade, ak je x menšie, cieľ x musí ležať v ľavej (spodnej) polovici. Takže použijeme algoritmus pre ľavú polovicu.
Program Python pre binárne vyhľadávanie pomocou rekurzívneho
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'> )> |
Výkon
Element is present at index 3
Časová zložitosť : O (log n)
Pomocný priestor : O(logn) [POZNÁMKA: Rekurzia vytvorí zásobník hovorov]
Program Python pre binárne vyhľadávanie pomocou iterácie
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 # znamená, že x je prítomné uprostred else: return mid # Ak sa dostaneme sem, potom prvok nebol prítomný return -1 # Testovacie pole arr = [ 2, 3, 4, 10, 40 ] x = 10 # Výsledok volania funkcie = binary_search(arr, x) if result != -1: print('Element je prítomný na indexe', str(result)) else: print('Element nie je prítomný v poli ')> |
Výkon
Element is present at index 3
Časová zložitosť : O (log n)
Pomocný priestor : O(1)
Program Python pre binárne vyhľadávanie Pomocou vstavaného modulu bisect
Postup krok za krokom:
- Kód importuje modul bisect, ktorý poskytuje podporu pre binárne vyhľadávanie.
- Je definovaná funkcia binary_search_bisect(), ktorá berie pole arr a prvok na vyhľadávanie x ako vstupy.
- Funkcia volá funkciu bisect_left() modulu bisect, ktorá nájde pozíciu prvku v zoradenom poli arr, kde by sa malo vložiť x, aby sa zachovalo zoradené poradie. Ak je prvok už prítomný v poli, táto funkcia vráti jeho pozíciu.
- Funkcia potom skontroluje, či je vrátený index i v rozsahu poľa a či sa prvok na tomto indexe rovná x.
- Ak je podmienka pravdivá, funkcia vráti index i ako pozíciu prvku v poli.
- Ak je podmienka nepravdivá, funkcia vráti hodnotu -1, čo znamená, že prvok nie je prítomný v poli.
- Kód potom definuje pole arr a prvok x na vyhľadávanie.
- Funkcia binary_search_bisect() sa volá s arr a x ako vstupmi a vrátený výsledok sa uloží do premennej result.
- Kód potom skontroluje, či sa výsledok nerovná -1, čo znamená, že prvok je prítomný v poli. Ak má hodnotu true, vypíše polohu prvku v poli.
- Ak je výsledok rovný -1, kód vypíše správu, že prvok nie je prítomný v poli.
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'> )> |
Výkon
Element is present at index 3
Časová zložitosť : O (log n)
Pomocný priestor : O(1)
