logo

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.

  1. Vertaa x:ää keskielementtiin.
  2. Jos x vastaa keskimmäistä elementtiä, palautetaan keskiindeksi.
  3. 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.
  4. 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>>>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'>)>



>

java enums

>

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


jos muuten lauseke java



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

> 

Element is present at index 3>

Aika monimutkaisuus : O(log n)

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


kapselointi javassa



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

kuinka sulkea kehittäjätila
>

>

Lähtö

Element is present at index 3>

Aika monimutkaisuus : O(log n)

Aputila : O(1)