PROGRAM PYTHON ZA BINARNO ISKANJE (REKURZIVNO IN ITERATIVNO)

Na kratko, ta iskalni algoritem izkorišča zbirko elementov, ki je že razvrščena tako, da prezre polovico elementov po samo eni primerjavi.

Primerjaj x s srednjim elementom.
Če se x ujema s srednjim elementom, vrnemo srednji indeks.
V nasprotnem primeru, če je x večji od srednjega elementa, lahko x leži le v desni (večji) polovici podniza za srednjim elementom. Nato ponovno uporabimo algoritem za desno polovico.
Če je x manjši, mora biti tarča x v levi (spodnji) polovici. Zato uporabimo algoritem za levo polovico.

Program Python za binarno iskanje z uporabo rekurzivnega

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'> )>

Izhod

Element is present at index 3

Časovna zapletenost : O(log n)

Pomožni prostor : O(logn) [OPOMBA: Rekurzija ustvari sklad klicev]

Program Python za binarno iskanje z uporabo iterative

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 # pomeni, da je x prisoten na mid else: return mid # Če pridemo do sem, potem element ni bil prisoten return -1 # Test array arr = [ 2, 3, 4, 10, 40 ] x = 10 # Rezultat klica funkcije = binary_search(arr, x) if result != -1: print('Element je prisoten v indeksu', str(rezultat)) else: print('Element ni prisoten v matriki ')>

Izhod

Element is present at index 3

Časovna zapletenost : O(log n)

Pomožni prostor : O(1)

Program Python za binarno iskanje z uporabo vgrajenega modula bisect

Pristop korak za korakom:

Koda uvozi modul bisect, ki zagotavlja podporo za binarno iskanje.
Definirana je funkcija binary_search_bisect(), ki kot vhodne podatke vzame matriko arr in element za iskanje x.
Funkcija pokliče funkcijo bisect_left() modula bisect, ki najde položaj elementa v razvrščeni matriki arr, kamor je treba vstaviti x, da se ohrani razvrščeni vrstni red. Če je element že prisoten v matriki, bo ta funkcija vrnila njegov položaj.
Funkcija nato preveri, ali je vrnjeni indeks i znotraj obsega matrike in ali je element pri tem indeksu enak x.
Če je pogoj resničen, potem funkcija vrne indeks i kot položaj elementa v matriki.
Če je pogoj napačen, potem funkcija vrne -1, kar pomeni, da element ni prisoten v matriki.
Koda nato definira matriko arr in element x za iskanje.
Funkcija binary_search_bisect() se pokliče z arr in x kot vhodoma, vrnjeni rezultat pa se shrani v spremenljivko rezultata.
Koda nato preveri, ali rezultat ni enak -1, kar pomeni, da je element prisoten v matriki. Če je res, natisne položaj elementa v matriki.
Če je rezultat enak -1, potem koda natisne sporočilo, da element ni prisoten v matriki.

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'> )>

Izhod