En af de mest fundamentale algoritmer inden for datalogi er den binære søgealgoritme. Du kan implementere binær søgning ved hjælp af to metoder: den iterative metode og den rekursive metode. Mens begge metoder har samme tidskompleksitet, er den iterative metode meget mere effektiv med hensyn til rumkompleksitet.

Den iterative metode har en rumkompleksitet på O(1) i forhold til O(logn) fremstillet ved den rekursive metode. Så hvordan kan du implementere den binære søgealgoritme ved hjælp af den iterative metode i C, C++ og Python?

Hvad er binær søgning?

Binær søgning også kendt som halvintervalsøgning, logaritmisk søgning eller binær chop er en algoritme, der søger og returnerer et elements position i et sorteret array. Søgeelementet sammenlignes med det midterste element. Tager du gennemsnittet af de nedre og øvre grænser, kan du finde de midterste elementer.

Hvis søgeelementet er større end det midterste element, betyder det, at alle elementerne på venstre side er mindre end søgeelementet. Så kontrollen skifter til højre side af arrayet (hvis arrayet er i stigende rækkefølge) ved at øge den nedre grænse til den næste position af det midterste element.

instagram viewer

På samme måde, hvis søgeelementet er mindre end det midterste element, betyder det, at alle elementerne på højre side er større end søgeelementet. Så kontrollen skifter til venstre del af arrayet ved at ændre den øvre grænse til den tidligere position af det midterste element.

Dette reducerer antallet af sammenligninger drastisk i forhold til lineær søgning implementering hvor antallet af sammenligninger er lig med antallet af elementer i worst-case scenariet. Denne metode viser sig meget nyttig til at finde numre i en telefonbog eller ord i en ordbog.

Her er en diagrammatisk fremstilling af Binær søgealgoritme:

Binær søgning ved hjælp af C

Følg disse trin for at implementere binær søgning ved hjælp af C:

Hele kildekoden til det binære søgeprogram ved hjælp af C, C++, Java og Python er til stede i dette GitHub-depot.

Programmet definerer en funktion, binær søgning(), der returnerer enten indekset for den fundne værdi eller -1 hvis den ikke er til stede:

#omfatte <stdio.h>
intbinær søgning(int arr[], int arr_size, int søgenummer){
/*... */
}

Funktionen fungerer ved iterativt at indsnævre søgerummet. Da binær søgning virker på sorterede arrays, kan du beregne midten, som ellers ikke giver mening. Du kan enten bede brugeren om et sorteret array eller bruge sorteringsalgoritmer såsom Bubble eller Selection sort.

Det lav og høj variabler gemmer de indekser, der repræsenterer grænserne for det aktuelle søgeområde. midt gemmer indekset i midten:

int lav = 0, høj = arr_size - 1, midt;

Det vigtigste mens() loop vil indsnævre søgeområdet. Hvis værdien af ​​det lave indeks nogensinde bliver større end det høje indeks, er søgepladsen opbrugt, så værdien kan ikke være til stede.

mens (lav <= høj) {
/* fortsætter... [1] */
 }
Vend tilbage-1;

Efter opdatering af midtpunktet i begyndelsen af ​​løkken, er der tre mulige udfald:

  1. Hvis værdien i midtpunktet er den, vi leder efter, skal du returnere det indeks.
  2. Hvis midtpunktsværdien er større end den, vi leder efter, skal du reducere den høje.
  3. Hvis midtpunktsværdien er mindre, øges den lave. 
/* [1] ...fortsat */
 mid = (lav + (høj - lav)) / 2;
if (arr[mid] == søgenummer)
Vend tilbage midten;
andethvis (arr[mid] > søgenummer)
 høj = midt - 1;
andet
 lav = mellem + 1;

Test funktionen med brugerinput. Brug scanf() for at få input fra kommandolinjen, inklusive matrixstørrelsen, dens indhold og et tal at søge efter:

intvigtigste(){
int arr[100], i, arr_size, search_number;
 printf("Indtast antallet af elementer: ");
 scanf("%d", &arr_size);
 printf("Indtast venligst tal: ");
for (i = 0; jeg < arr_størrelse; i++) {
 scanf("%d", &arr[i]);
 }


printf("Indtast nummer, der skal søges i: ");
 scanf("%d", &søgenummer);


i = binær søgning (arr, arr_size, search_number);


hvis (i==-1)
 printf("Nummer ikke til stede");
andet
 printf("Nummeret er til stede på position %d"i + 1);
Vend tilbage0;
}

Hvis du finder nummeret, skal du vise dets position eller indeks, ellers en meddelelse om, at nummeret ikke er til stede.

Binær søgning ved hjælp af C++

Du kan konvertere C-programmet til et C++-program ved at importere Input Output Stream og brug navneområde std for at undgå at gentage det flere gange i løbet af programmet.

#omfatte <iostream>
ved brug af navneområdestd;

Brug cout med udsugningsoperatør << i stedet for printf() og cin med indsættelsesoperatør >> i stedet for scanf() og dit C++ program er klar.

printf("Indtast antallet af elementer: ");
cout <<"Indtast antallet af elementer: ";
scanf("%d", &arr_size);
cin >> arr_størrelse;

Binær søgning ved hjælp af Python

Da Python ikke har indbygget understøttelse af arrays, skal du bruge lister. Definer en funktion, binær søgning(), der accepterer tre parametre, listen, dens størrelse og et tal, der skal søges efter:

defbinær søgning(arr, arr_size, search_number):
 lav = 0
 høj = arr_size - 1
mens lav <= høj:
 mellem = lav + (høj-lav)//2
 hvis arr[mid] == søgenummer:
Vend tilbage midt
elif arr[midt] > søgenummer:
 høj = midt - 1
andet:
 lav = mellem + 1
Vend tilbage-1

Initialiser to variable, lav og høj, for at tjene som den nedre og øvre grænse for listen. I lighed med C-implementeringen skal du bruge en mens sløjfe, der indsnævrer søgerummet. Initialiser midt for at gemme listens midterste værdi. Python leverer etageopdelingsoperatoren(//), der giver det størst mulige heltal.

Foretag sammenligningerne og indsnæv søgeområdet, indtil midterværdien er lig med søgetallet. Hvis søgenummeret ikke er til stede, vender kontrollen tilbage -1.

arr_size = int (input("Indtast antallet af elementer: "))
arr=[]
Print("Indtast venligst tal: ", ende="")
for i inden for rækkevidde (0,arr_size):
 arr.append(int(input()))
søgenummer = int (input("Indtast nummer, der skal søges i: "))
resultat = binær søgning (arr, arr_size, search_number)
hvis resultat == -1:
 Print("Nummer ikke til stede")
andet:
 print("Nummer er til stede på position ", (resultat + 1))

Test funktionen med brugerinput. Brug input() for at få listestørrelsen, dens indhold og et nummer at søge efter. Brug int() at typecaste det strenginput, der accepteres af Python som standard, til et heltal. For at tilføje numre til listen skal du bruge Tilføj() fungere.

Opkald binær søgning() og videregive argumenterne. Hvis du finder nummeret, skal du vise dets position eller indeks, ellers en meddelelse om, at nummeret ikke er til stede.

Output af binær søgealgoritme

Følgende er output fra den binære søgealgoritme, når elementet er til stede i arrayet:

Følgende er output fra den binære søgealgoritme, når elementet ikke er til stede i arrayet:

Lær de grundlæggende datastrukturer og algoritmer

Søgning er en af ​​de første algoritmer, du lærer og bliver ofte spurgt i kodningskonkurrencer, placeringer og interviews. Nogle andre algoritmer, du bør lære, er sortering, hashing, dynamisk programmering, strengmatchning og primalitetstestalgoritmer.

Derudover er det vigtigt at forstå tids- og rumkompleksiteten af ​​algoritmer. De er et af de mest afgørende begreber inden for datalogi til at bestemme effektiviteten af ​​enhver algoritme. Med viden om datastrukturer og algoritmer er du forpligtet til at bygge de bedste programmer.