Hva er binært søk?

Et binært søk er en søkende algoritme som brukes til å søke på målelementer i en beholder der det må ordnes elementer i stigende rekkefølge. Generelt brukes binært søk for å søke i indeksnummeret til målelementet i en sortert matrise.

Det binære søket bruker skillet og erobrer tilnærmingen, der den deler matrisen i like deler til den finner målelementet.

En binær søkealgoritme implementeres iterativ så vel som en rekursiv uttalelse. Binært søk er mer effektivt og raskere sammenlignet med lineær søk.

Binær søkealgoritme

1. Sorter og ordne elementene i matrisen arr i stigende rekkefølge.
2. Algoritmene sammenligner mellomelementet n med målelementet mål.
3. Algoritmen returnerer posisjonsindeksen til det midterste elementet hvis målelementet er funnet å være lik det midterste elementet,
4. Algoritmen søker i den nedre halvdelen av matrisen hvis målelementet er mindre enn midtelementet.
5. Algoritmen søker i den øvre halvdelen av matrisen hvis målelementet er større enn midtelementet.
6. Algoritmen gjentar stadig fjerde og 5. trinn til matrisens lengde blir en eller mindre enn 1.

Mot slutten returneres enten indeksverdien til elementet, eller elementet eksisterer ikke i matrisen.

Binær søk pseudokode

Iterativ

funksjon binary_search (arr, n, mål) er
Venstre: = 0
Til høyre: = n - 1
mens du er venstre ≤ høyre gjør
Midt: = gulv ((venstre + høyre) / 2)
Hvis arr [midt] mål da
Til høyre: = midten - 1
ellers:
returner midten
Returner mislykket

Tilbakevendende

funksjon binary_search (arr, venstre, høyre, mål) er
Hvis høyre> = venstre
midten = (venstre+høyre) // 2
Hvis arr [midt] == ​​mål
returner midten
ellers hvis arr [midt]> Tarrget
Return Binary_search (arr, lav, midt-1, mål)
ellers
Returner Binary_search (arr, mid+1, til høyre, mål)
ellers
Returner mislykket

Implementere binærsøk i Python

Iterativ
I den iterative tilnærmingen bruker vi løkkene til å implementere binær søk.

def binary_search (arr, n, mål):
Venstre = 0
høyre = n-1
midten = 0
mens du er igjen<=right:
midten = (høyre+venstre) // 2
#Hvis det midterste elementet er lik målelementet
Hvis arr [midt] == ​​mål:
returner midten
# Hvis målelementet er større enn mellomelementet
elif arr [midt]< target:
Venstre = midten+1
# Hvis målelementet er mindre enn mellomelement
ellers:
Høyre = Midt-1
# Hvis målelementet ikke er til stede i matrisen
Retur -1
if __name__ == '__main__':
# Sortert matrise
sortert_arr = [0,4,7,10,14,23,45,47,53]
# lengden på matrisen
n = len (sortert_arr)
#element å søke
mål = 47
posisjon = binary_search (sorted_arr, n, mål)
Hvis posisjon != -1:
print (f "element mål til stede på indeks posisjon")
ellers:
PRINT (F "Element Target er ikke til stede i Array")

Produksjon

Element 47 til stede ved indeks 7

Tilbakevendende
I rekursiv i stedet for å bruke sløyfe, kaller vi stadig funksjonen igjen og igjen til grunntilstanden blir fornøyd

def binary_search (arr, venstre, høyre, mål):
#Base -tilstand
Hvis RightTarget:
Returner Binary_search (arr, venstre, midt-1, mål)
#Hvis målelementet er mindre enn mellomelement
ellers:
Returner Binary_search (arr, midt+1, til høyre, mål)
if __name__ == '__main__':
# Sortert matrise
sortert_arr = [0,4,7,10,14,23,45,47,53]
Venstre = 0
høyre = len (sortert_arr) -1
#element å søke
mål = 47
posisjon = binary_search (sorted_arr, venstre, høyre, mål)
Hvis posisjon != -1:
print (f "element mål til stede på indeks posisjon")
ellers:
PRINT (F "Element Target er ikke til stede i Array")

Produksjon

Element 90 er ikke til stede i matrisen

Kompleksitet

Binær søk har en tidskompleksitet av O (log n), hvor n er antall elementer som er til stede i matrisen.

Binær søk har en romkompleksitet på O (1) fordi vi i algoritmen utfører søket på stedet.

Konklusjon

Binær søk er en av de beste og effektive søkealgoritmene. Tids- og romkompleksiteten til binær søk er også veldig lav; Den eneste forutsetningen for binær søk er at inngangsarrayen skal sorteres i stigende rekkefølge.