PYTHON-OHJELMA BINÄÄRIHAKUUN (REKURSIIVINEN JA ITERATIIVINEN)

Lyhyesti sanottuna tämä hakualgoritmi hyödyntää elementtikokoelmaa, joka on jo lajiteltu jättämällä huomioimatta puolet elementeistä yhden vertailun jälkeen.

Vertaa x:ää keskielementtiin.
Jos x vastaa keskimmäistä elementtiä, palautetaan keskiindeksi.
Muutoin jos x on suurempi kuin keskielementti, niin x voi sijaita vain oikeanpuoleisessa (suuremmassa) puolivälissä keskielementin jälkeen. Sitten käytämme algoritmia uudelleen oikealle puolikkaalle.
Muussa tapauksessa, jos x on pienempi, kohteen x on sijaittava vasemmalla (alemmalla) puoliskolla. Joten käytämme algoritmia vasemmalle puolikkaalle.

Python-ohjelma binäärihakuun rekursiivista käyttöä varten

Python 3

# 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>>> ,> str> (result))> else> :> > print> (> 'Element is not present in array'> )>

Lähtö

Element is present at index 3

Aika monimutkaisuus : O(log n)

Aputila : O(logn) [HUOM: Rekursio luo puhelupinon]

Python-ohjelma binäärihakuun käyttämällä iteratiivista

Python 3

# 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 # tarkoittaa x on läsnä mid else: return mid # Jos saavutamme tämän, elementtiä ei ollut läsnä return -1 # Test array arr = [ 2, 3, 4, 10, 40 ] x = 10 # Funktiokutsu tulos = binary_search(arr, x) if tulos != -1: print('Elementti on indeksissä', str(tulos)) else: print('Elementti ei ole taulukossa ')>>

>    
      
      Aputila     : O(1)  
      Python-ohjelma binäärihakuun Sisäänrakennetun bisect-moduulin avulla     
      Askel askeleelta lähestymistapa:     
     Koodi tuo bisect-moduulin, joka tukee binäärihakua.  
   Määritetään binary_search_bisect()-funktio, joka ottaa syötteinä taulukon arr ja elementin, jolla haetaan x.  
   Funktio kutsuu bisect_left()-funktiota bisect-moduulissa, joka etsii elementin sijainnin lajitetussa taulukossa arr, johon x tulisi lisätä, jotta järjestys säilyy. Jos elementti on jo taulukossa, tämä funktio palauttaa sijaintinsa.  
   Sitten funktio tarkistaa, onko palautettu indeksi i taulukon alueella ja onko kyseisen indeksin elementti yhtä suuri kuin x.  
   Jos ehto on tosi, funktio palauttaa indeksin i elementin sijainniksi taulukossa.  
   Jos ehto on epätosi, funktio palauttaa -1, mikä osoittaa, että elementtiä ei ole taulukossa.  
   Koodi määrittelee sitten taulukon arr ja etsittävän elementin x.  
   Binary_search_bisect()-funktiota kutsutaan syötteinä arr ja x ja palautettu tulos tallennetaan tulosmuuttujaan.  
   Sitten koodi tarkistaa, onko tulos eri kuin -1, mikä osoittaa, että elementti on taulukossa. Jos tosi, se tulostaa elementin sijainnin taulukossa.  
   Jos tulos on -1, koodi tulostaa viestin, että elementtiä ei ole taulukossa.  
  
  Python 3 
      
       
   
       
       
     
     
   
          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'>  )>     
  
  
   
      
    
      
    
  Lähtö    
  Element is present at index 3 
      Aika monimutkaisuus     : O(log n)  
      Aputila     : O(1)