En av de mest grunnleggende algoritmene innen informatikk er Binary Search-algoritmen. Du kan implementere binært søk ved å bruke to metoder: den iterative metoden og den rekursive metoden. Mens begge metodene har samme tidskompleksitet, er den iterative metoden mye mer effektiv når det gjelder romkompleksitet.

Den iterative metoden har en romkompleksitet på O(1) sammenlignet med O(logg) produsert etter den rekursive metoden. Så hvordan kan du implementere den binære søkealgoritmen ved å bruke den iterative metoden i C, C++ og Python?

Hva er binært søk?

Binært søk også kjent som halvintervallsøk, logaritmisk søk ​​eller binært chop er en algoritme som søker og returnerer posisjonen til et element i en sortert matrise. Søkeelementet sammenlignes med midtelementet. Ved å ta gjennomsnittet av de nedre og øvre grensene, kan du finne de midterste elementene.

Hvis søkeelementet er større enn det midterste elementet, betyr det at alle elementene på venstre side er mindre enn søkeelementet. Så kontrollen skifter til høyre side av matrisen (hvis matrisen er i stigende rekkefølge) ved å øke den nedre grensen til neste posisjon av midtelementet.

På samme måte, hvis søkeelementet er mindre enn det midterste elementet, betyr det at alle elementene på høyre side er større enn søkeelementet. Så kontrollen skifter til venstre del av matrisen ved å endre den øvre grensen til den forrige posisjonen til midtelementet.

Dette reduserer antallet sammenligninger drastisk sammenlignet med lineær søkeimplementering der hvor antall sammenligninger er lik antall elementer i verste fall. Denne metoden viser seg å være svært nyttig for å finne tall i en telefonbok eller ord i en ordbok.

Her er en diagrammatisk fremstilling av Binær søkealgoritme:

Binært søk med C

Følg disse trinnene for å implementere binært søk med C:

Hele kildekoden til det binære søkeprogrammet som bruker C, C++, Java og Python er til stede i dette GitHub-depot.

Programmet definerer en funksjon, binært søk(), som returnerer enten indeksen for den funnet verdien eller -1 hvis den ikke er tilstede:

#inkludere <stdio.h>
intbinært søk(int arr[], int arr_size, int search_number){
/*... */
}

Funksjonen fungerer ved iterativt å begrense søkeområdet. Siden binært søk fungerer på sorterte arrays, kan du beregne midten som ellers ikke gir mening. Du kan enten be brukeren om en sortert matrise eller bruke sorteringsalgoritmer som Bubble eller Selection sort.

De lav og høy variabler lagrer indeksene som representerer grensene for gjeldende søkerom. midten lagrer indeksen i midten:

int lav = 0, høy = arr_size - 1, midten;

Hoved samtidig som() loop vil begrense søkeområdet. Hvis verdien av den lave indeksen noen gang blir større enn den høye indeksen, er søkeplassen oppbrukt, så verdien kan ikke være tilstede.

samtidig som (lav <= høy) {
/* fortsetter... [1] */
 }
komme tilbake-1;

Etter å ha oppdatert midtpunktet i begynnelsen av loopen, er det tre mulige utfall:

  1. Hvis verdien ved midtpunktet er den vi ser etter, returner den indeksen.
  2. Hvis midtpunktsverdien er større enn den vi ser etter, reduser den høye.
  3. Hvis midtpunktsverdien er mindre, øk den lave. 
/* [1] ...fortsatt */
 mid = (lav + (høy - lav)) / 2;
if (arr[midt] == ​​søkenummer)
komme tilbake midten;
ellershvis (arr[midt] > søkenummer)
 høy = midt - 1;
ellers
 lav = middels + 1;

Test funksjonen med brukerinndata. Bruk scanf() for å få inndata fra kommandolinjen, inkludert matrisestørrelsen, innholdet og et tall å søke etter:

inthoved-(){
int arr[100], i, arr_size, search_number;
 printf("Skriv inn antall elementer: ");
 scanf("%d", &arr_size);
 printf("Vennligst skriv inn tall: ");
for (i = 0; Jeg < arr_size; i++) {
 scanf("%d", &arr[i]);
 }


printf("Skriv inn nummeret som skal søkes: ");
 scanf("%d", &søk_nummer);


i = binært søk (arr, arr_size, search_number);


hvis (i==-1)
 printf("Nummer ikke til stede");
ellers
 printf("Tallet er tilstede på posisjon %d"i + 1);
komme tilbake0;
}

Hvis du finner nummeret, vis dets posisjon eller indeks, ellers en melding som sier at nummeret ikke er til stede.

Binært søk med C++

Du kan konvertere C-programmet til et C++-program ved å importere Input Output Stream og bruk navneområde std for å unngå å gjenta det flere ganger gjennom programmet.

#inkludere <iostream>
ved hjelp av navneområdestd;

Bruk cout med avtrekksoperatør << i stedet for printf() og cin med innsettingsoperatør >> i stedet for scanf() og C++-programmet er klart.

printf("Skriv inn antall elementer: ");
cout <<"Skriv inn antall elementer: ";
scanf("%d", &arr_size);
cin >> arr_size;

Binært søk med Python

Siden Python ikke har innebygd støtte for arrays, bruk lister. Definer en funksjon, binært søk(), som godtar tre parametere, listen, størrelsen og et tall å søke etter:

defbinært søk(arr, arr_size, search_number):
 lav = 0
 høy = arr_size - 1
samtidig som lav <= høy:
 mellom = lav + (høy-lav)//2
 if arr[midt] == ​​søk_nummer:
komme tilbake midten
elif arr[midt] > søkenummer:
 høy = midt - 1
ellers:
 lav = middels + 1
komme tilbake-1

Initialiser to variabler, lav og høy, for å tjene som nedre og øvre grense for listen. I likhet med C-implementeringen, bruk en samtidig som løkke som begrenser søkeområdet. Initialiser midten for å lagre den midterste verdien av listen. Python gir etasjedelingsoperatoren(//) som gir størst mulig heltall.

Foreta sammenligningene og begrense søkeområdet til midtverdien er lik søketallet. Hvis søkenummeret ikke er til stede, kommer kontrollen tilbake -1.

arr_size = int (input("Skriv inn antall elementer: "))
arr=[]
skrive ut("Vennligst skriv inn tall: ", slutt="")
for i innen rekkevidde (0,arr_size):
 arr.append(int(input()))
søk_nummer = int (input("Skriv inn nummeret som skal søkes: "))
resultat = binært søk (arr, arr_size, search_number)
hvis resultat == -1:
 skrive ut("Nummer ikke til stede")
ellers:
 print("Tall er tilstede i posisjon ", (resultat + 1))

Test funksjonen med brukerinndata. Bruk input() for å få listestørrelsen, innholdet og et nummer å søke etter. Bruk int() for å typecaste strenginndata som er akseptert av Python som standard til et heltall. For å legge til tall på listen, bruk legge til() funksjon.

Anrop binært søk() og passere argumentene. Hvis du finner nummeret, vis dets posisjon eller indeks, ellers en melding som sier at nummeret ikke er til stede.

Utdata fra binær søkealgoritme

Følgende er utdataene fra den binære søkealgoritmen når elementet er tilstede i matrisen:

Følgende er utdata fra binærsøkealgoritmen når elementet ikke er tilstede i matrisen:

Lær de grunnleggende datastrukturene og algoritmene

Søking er en av de første algoritmene du lærer og blir ofte spurt i kodekonkurranser, plasseringer og intervjuer. Noen andre algoritmer du bør lære er algoritmer for sortering, hashing, dynamisk programmering, strengmatching og primalitetstesting.

I tillegg er det viktig å forstå tids- og romkompleksiteten til algoritmer. De er et av de mest avgjørende konseptene innen informatikk for å bestemme effektiviteten til enhver algoritme. Med kunnskap om datastrukturer og algoritmer, er du nødt til å bygge de beste programmene.