„Python“ programa dvejetainei paieškai (rekursyvinė ir kartotinė)
Trumpai tariant, šis paieškos algoritmas naudojasi elementų rinkiniu, kuris jau yra surūšiuotas ignoruojant pusę elementų po vieno palyginimo.
- Palyginkite x su viduriniu elementu.
- Jei x atitinka vidurinį elementą, grąžiname vidurinį indeksą.
- Kitu atveju, jei x yra didesnis už vidurinį elementą, tada x gali būti tik dešinėje (didesnėje) pusėje po vidurio elemento. Tada dešiniajai pusei vėl taikome algoritmą.
- Kitu atveju, jei x yra mažesnis, taikinys x turi būti kairėje (apatinėje) pusėje. Taigi mes taikome kairiosios pusės algoritmą.
Python programa, skirta dvejetainei paieškai naudojant rekursyvų
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>>> ,> str> (result))> else> :> > print> (> 'Element is not present in array'> )> |
Išvestis
Element is present at index 3
Laiko sudėtingumas : O(log n)
Pagalbinė erdvė : O(prisijungti) [PASTABA: rekursija sukuria skambučių krūvą]
„Python“ programa, skirta dvejetainei paieškai naudojant iteracinę funkciją
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: aukštas = vidutinis - 1 # reiškia, kad x yra viduryje. Kita: return mid # Jei pasiekiame čia, tada elemento nebuvo return -1 # Bandomasis masyvas arr = [ 2, 3, 4, 10, 40 ] x = 10 # Funkcijos iškvietimo rezultatas = binary_search(arr, x) if rezultatas != -1: print('Elementas yra indekse', str(rezultatas)) else: print('Elemento nėra masyve ')>> |
>
Pagalbinė erdvė : O(1) „Python“ programa dvejetainei paieškai Naudojant integruotą bisect modulį
Žingsnis po žingsnio požiūris:
- Kodas importuoja bisect modulį, kuris palaiko dvejetainę paiešką.
- Apibrėžiama funkcija binary_search_bisect(), kuri kaip įvestis naudoja masyvą arr ir elementą x paieškai.
- Funkcija iškviečia pusiausvyros modulio funkciją bisect_left(), kuri nustato elemento padėtį surūšiuotame masyve arr, kur x turėtų būti įterptas, kad būtų išlaikyta rūšiavimo tvarka. Jei elementas jau yra masyve, ši funkcija grąžins savo poziciją.
- Tada funkcija patikrina, ar grąžintas indeksas i yra masyvo diapazone ir ar to indekso elementas yra lygus x.
- Jei sąlyga teisinga, funkcija grąžina indeksą i kaip elemento padėtį masyve.
- Jei sąlyga klaidinga, funkcija grąžina -1, nurodydama, kad elemento masyve nėra.
- Tada kodas apibrėžia masyvą arr ir elementą x, kurį reikia ieškoti.
- Funkcija binary_search_bisect() iškviečiama naudojant arr ir x įvestis, o grąžintas rezultatas išsaugomas rezultato kintamajame.
- Tada kodas patikrina, ar rezultatas nėra lygus -1, nurodant, kad elementas yra masyve. Jei tiesa, ji atspausdina elemento padėtį masyve.
- Jei rezultatas lygus -1, tada kodas išspausdina pranešimą, kad elemento masyve nėra.
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'>)>
Išvestis
Element is present at index 3Laiko sudėtingumas : O(log n)
Pagalbinė erdvė : O(1)
