Een van de meest fundamentele algoritmen in de informatica is het binaire zoekalgoritme. U kunt binair zoeken op twee manieren implementeren: de iteratieve methode en de recursieve methode. Hoewel beide methoden dezelfde tijdscomplexiteit hebben, is de iteratieve methode veel efficiënter in termen van ruimtecomplexiteit.

De iteratieve methode heeft een ruimtecomplexiteit van O(1) in vergelijking met O(aanmelden) geproduceerd door de recursieve methode. Dus, hoe kun je het Binary Search-algoritme implementeren met behulp van de iteratieve methode in C, C++ en Python?

Wat is binair zoeken?

Binair zoeken, ook wel half-interval zoeken, logaritmisch zoeken of binair hakken genoemd, is een algoritme dat de positie van een element in een gesorteerde array zoekt en retourneert. Het zoekelement wordt vergeleken met het middelste element. Door het gemiddelde van de onder- en bovengrenzen te nemen, kunt u de middelste elementen vinden.

Als het zoekelement groter is dan het middelste element, betekent dit dat alle elementen aan de linkerkant kleiner zijn dan het zoekelement. De besturing verschuift dus naar de rechterkant van de array (als de array in oplopende volgorde staat) door de ondergrens te verhogen naar de volgende positie van het middelste element.

instagram viewer

Evenzo, als het zoekelement kleiner is dan het middelste element, betekent dit dat alle elementen aan de rechterkant groter zijn dan het zoekelement. De besturing verschuift dus naar het linkerdeel van de array door de bovengrens te wijzigen in de vorige positie van het middelste element.

Dit vermindert het aantal vergelijkingen drastisch in vergelijking met lineaire zoekimplementatie waarbij het aantal vergelijkingen gelijk is aan het aantal elementen in het worstcasescenario. Deze methode blijkt erg handig voor het vinden van nummers in een telefoonboek of woorden in een woordenboek.

Hier is een schematische weergave van de Binair zoekalgoritme:

Binair zoeken met behulp van C

Volg deze stappen om Binary Search te implementeren met C:

Hierin is de volledige broncode van het binaire zoekprogramma met behulp van C, C ++, Java en Python aanwezig GitHub-opslagplaats.

Het programma definieert een functie, Binaire zoekopdracht(), die de index van de gevonden waarde of retourneert -1 als het niet aanwezig is:

#erbij betrekken <standaard.h>
intBinaire zoekopdracht(int arr[], int arr_size, int zoeknummer){
/*... */
}

De functie werkt door de zoekruimte iteratief te verkleinen. Omdat binair zoeken werkt op gesorteerde arrays, kunt u het midden berekenen, wat anders niet logisch is. U kunt de gebruiker om een ​​gesorteerde array vragen of sorteeralgoritmen gebruiken, zoals Bubble- of Selection-sort.

De laag En hoog variabelen slaan de indexen op die de grenzen van de huidige zoekruimte vertegenwoordigen. midden slaat de index in het midden op:

int laag = 0, hoog = arr_size - 1, midden;

De belangrijkste terwijl() loop verkleint de zoekruimte. Als de waarde van de lage index ooit groter wordt dan de hoge index, dan is de zoekruimte uitgeput en kan de waarde dus niet aanwezig zijn.

terwijl (laag <= hoog) {
/* gaat verder... [1] */
 }
opbrengst-1;

Na het bijwerken van het middelpunt aan het begin van de lus zijn er drie mogelijke uitkomsten:

  1. Als de waarde in het midden de waarde is waarnaar we op zoek zijn, retourneert u die index.
  2. Als de middelste waarde groter is dan degene waarnaar we op zoek zijn, verlaagt u de hoge waarde.
  3. Als de middelpuntwaarde lager is, verhoog dan de lage waarde. 
/* [1] ...vervolg */
 midden = (laag + (hoog - laag)) / 2;
als (arr[mid] == zoeknummer)
opbrengst midden;
andersals (arr[mid] > zoeknummer)
 hoog = midden - 1;
anders
 laag = midden + 1;

Test de functie met gebruikersinvoer. Gebruik scannen() om invoer van de opdrachtregel te krijgen, inclusief de grootte van de array, de inhoud ervan en een nummer om naar te zoeken:

intvoornaamst(){
int arr[100], i, arr_size, zoeknummer;
 printf("Vul het aantal elementen in: ");
 scannen("%D", &arr_grootte);
 printf("Gelieve cijfers in te vullen: ");
voor (i = 0; i < arr_grootte; ik++) {
 scannen("%D", &arr[i]);
 }


printf("Voer het te zoeken nummer in: ");
 scannen("%D", &zoeknummer);


i = binair zoeken (arr, arr_size, zoek_nummer);


als (i==-1)
 printf("Nummer niet aanwezig");
anders
 printf("Nummer is aanwezig op positie %d", ik + 1);
opbrengst0;
}

Als u het nummer vindt, geeft u de positie of index weer, anders wordt er een bericht weergegeven dat het nummer niet aanwezig is.

Binair zoeken met C++

U kunt het C-programma converteren naar een C++-programma door het Invoer Uitvoerstroom En gebruik naamruimte std om herhaling tijdens het programma meerdere keren te voorkomen.

#erbij betrekken <iostream>
gebruik makend van naamruimtesoa;

Gebruik cout met extractie-operator << in plaats van printf() En cin met invoegoperator >> in plaats van scannen() en je C++ programma is klaar.

printf("Vul het aantal elementen in: ");
cout <<"Vul het aantal elementen in: ";
scannen("%D", &arr_grootte);
cin >> arr_grootte;

Binair zoeken met behulp van Python

Gebruik lijsten, aangezien Python geen ingebouwde ondersteuning voor arrays heeft. Definieer een functie, Binaire zoekopdracht(), dat drie parameters accepteert, de lijst, de grootte en een nummer om naar te zoeken:

defBinaire zoekopdracht(arr, arr_size, zoeknummer):
 laag = 0
 hoog = arr_size - 1
terwijl laag <= hoog:
 midden = laag + (hoog-laag)//2
 if arr[mid] == zoeknummer:
opbrengst midden
elif arr[mid] > zoeknummer:
 hoog = midden - 1
anders:
 laag = midden + 1
opbrengst-1

Initialiseer twee variabelen, laag En hoog, om te dienen als de onder- en bovengrens van de lijst. Net als bij de C-implementatie, gebruik a terwijl lus die de zoekruimte vernauwt. Initialiseren midden om de middelste waarde van de lijst op te slaan. Python biedt de verdiepingsdelingsoperator (//) die het grootst mogelijke gehele getal oplevert.

Maak de vergelijkingen en verklein de zoekruimte totdat de middelste waarde gelijk is aan het zoeknummer. Als het zoeknummer niet aanwezig is, keert de besturing terug -1.

arr_size = int (invoer("Vul het aantal elementen in: "))
arr=[]
afdrukken("Gelieve cijfers in te vullen: ", einde="")
voor i in bereik (0,arr_size):
 arr.toevoegen(int(invoer()))
zoeknummer = int (invoer("Voer het te zoeken nummer in: "))
result = binarySearch (arr, arr_size, search_number)
als resultaat == -1:
 afdrukken("Nummer niet aanwezig")
anders:
 print("Nummer is aanwezig op positie ", (resultaat + 1))

Test de functie met gebruikersinvoer. Gebruik invoer() om de lijstgrootte, de inhoud en een nummer om naar te zoeken te krijgen. Gebruik int() om de tekenreeksinvoer die door Python als standaard wordt geaccepteerd, om te zetten in een geheel getal. Gebruik de om nummers aan de lijst toe te voegen toevoegen() functie.

Telefoongesprek Binaire zoekopdracht() en geef de argumenten door. Als u het nummer vindt, geeft u de positie of index weer, anders wordt er een bericht weergegeven dat het nummer niet aanwezig is.

Uitvoer van binair zoekalgoritme

Het volgende is de uitvoer van het binaire zoekalgoritme wanneer het element aanwezig is in de array:

Het volgende is de uitvoer van het binaire zoekalgoritme wanneer het element niet aanwezig is in de array:

Leer de fundamentele gegevensstructuren en algoritmen

Zoeken is een van de eerste algoritmen die je leert en wordt vaak gevraagd in programmeerwedstrijden, plaatsingen en interviews. Enkele andere algoritmen die u zou moeten leren, zijn sorteer-, hashing-, dynamisch programmeren-, string-matching- en primaliteitstestalgoritmen.

Bovendien is het essentieel om de tijd- en ruimtecomplexiteit van algoritmen te begrijpen. Ze zijn een van de meest cruciale concepten in de informatica bij het bepalen van de efficiëntie van elk algoritme. Met kennis van datastructuren en algoritmen bouw je gegarandeerd de beste programma's.