Python-program for binært søk (rekursivt og iterativt)
I et nøtteskall drar denne søkealgoritmen fordel av en samling av elementer som allerede er sortert ved å ignorere halvparten av elementene etter bare én sammenligning.
- Sammenlign x med det midterste elementet.
- Hvis x samsvarer med det midterste elementet, returnerer vi midtindeksen.
- Ellers hvis x er større enn det midterste elementet, så kan x bare ligge i høyre (større) halvundergruppe etter midtelementet. Så bruker vi algoritmen igjen for høyre halvdel.
- Ellers hvis x er mindre, må målet x ligge i venstre (nedre) halvdel. Så vi bruker algoritmen for venstre halvdel.
Python-program for binært søk ved bruk av rekursivt
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'> )> |
Produksjon
Element is present at index 3
Tidskompleksitet : O(log n)
Auxiliary Space : O(logg) [MERK: rekursjon oppretter anropsstabel]
Python-program for binært søk ved hjelp av iterativ
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: høy = mid - 1 # betyr at x er tilstede ved mid else: return mid # Hvis vi kommer hit, så var ikke elementet til stede return -1 # Test array arr = [ 2, 3, 4, 10, 40 ] x = 10 # Funksjonsanropsresultat = binært_søk(arr, x) hvis resultat != -1: print('Element er til stede i indeks', str(resultat)) else: print('Element er ikke til stede i array' ')> |
Produksjon
Element is present at index 3
Tidskompleksitet : O(log n)
Auxiliary Space : O(1)
Python-program for binært søk Ved hjelp av den innebygde halveringsmodulen
Steg for steg tilnærming:
- Koden importerer halveringsmodulen som gir støtte for binært søk.
- Funksjonen binary_search_bisect() er definert som tar en array arr og elementet for å søke x som innganger.
- Funksjonen kaller bisect_left()-funksjonen til bisect-modulen som finner posisjonen til elementet i den sorterte matrisen arr hvor x skal settes inn for å opprettholde den sorterte rekkefølgen. Hvis elementet allerede er til stede i matrisen, vil denne funksjonen returnere sin posisjon.
- Funksjonen sjekker deretter om den returnerte indeksen i er innenfor rekkevidden til matrisen og om elementet ved den indeksen er lik x.
- Hvis betingelsen er sann, returnerer funksjonen indeksen i som posisjonen til elementet i matrisen.
- Hvis betingelsen er usann, returnerer funksjonen -1 som indikerer at elementet ikke er til stede i matrisen.
- Koden definerer deretter en array arr og et element x for å søke.
- Funksjonen binary_search_bisect() kalles med arr og x som innganger og det returnerte resultatet lagres i resultatvariabelen.
- Koden sjekker deretter om resultatet ikke er lik -1, noe som indikerer at elementet er tilstede i matrisen. Hvis det er sant, skriver den ut posisjonen til elementet i matrisen.
- Hvis resultatet er lik -1, skriver koden ut en melding om at elementet ikke er til stede i matrisen.
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'> )> |
Produksjon
Element is present at index 3
Tidskompleksitet : O(log n)
Auxiliary Space : O(1)
