Üks arvutiteaduse põhilisemaid algoritme on binaarotsingu algoritm. Binaarse otsingu saate rakendada kahe meetodi abil: iteratiivne meetod ja rekursiivne meetod. Kuigi mõlemal meetodil on sama ajaline keerukus, on iteratiivne meetod ruumilise keerukuse seisukohalt palju tõhusam.

Iteratiivsel meetodil on ruumi keerukus O(1) võrreldes O (logi sisse) toodetud rekursiivsel meetodil. Niisiis, kuidas saate rakendada binaarse otsingu algoritmi iteratiivse meetodi abil C, C++ ja Pythonis?

Mis on binaarne otsing?

Binaarne otsing, tuntud ka kui poolintervallotsing, logaritmiline otsing või kahendjaotus, on algoritm, mis otsib ja tagastab sorteeritud massiivi elemendi asukoha. Otsinguelementi võrreldakse keskmise elemendiga. Võttes alumise ja ülemise piiri keskmise, leiate keskmised elemendid.

Kui otsinguelement on suurem kui keskmine element, tähendab see, et kõik vasakpoolsed elemendid on otsinguelemendist väiksemad. Seega nihkub juhtelement massiivi paremale poolele (kui massiiv on kasvavas järjekorras), suurendades alumist piiri keskmise elemendi järgmise positsioonini.

instagram viewer

Samamoodi, kui otsinguelement on keskmisest elemendist väiksem, tähendab see, et kõik paremal pool olevad elemendid on otsinguelemendist suuremad. Seega nihkub juhtelement massiivi vasakpoolsesse ossa, muutes ülemise piiri keskmise elemendi eelmisele positsioonile.

See vähendab oluliselt võrdluste arvu võrreldes lineaarse otsingu rakendamine kus võrdluste arv võrdub halvima stsenaariumi elementide arvuga. See meetod osutub väga kasulikuks numbrite leidmiseks telefoniraamatust või sõnade leidmiseks sõnastikust.

Siin on skemaatiline esitus Binaarne otsingu algoritm:

Binaarne otsing kasutades C

Järgige neid samme, et rakendada binaarotsingut kasutades C:

Selles on olemas kogu C-, C++-, Java- ja Pythoni binaarse otsinguprogrammi lähtekood GitHubi hoidla.

Programm määratleb funktsiooni, binaarne otsing (), mis tagastab kas leitud väärtuse indeksi või -1 kui seda pole:

#kaasa <stdio.h>
intbinaarne otsing(int arr[], int arr_size, int otsingu_number){
/*... */
}

Funktsioon töötab iteratiivselt otsinguruumi kitsendades. Kuna binaarne otsing töötab sorteeritud massiividel, saate arvutada keskmise, millel pole muidu mõtet. Võite küsida kasutajalt sorteeritud massiivi või kasutada sortimisalgoritme, näiteks mull- või valikusortimist.

The madal ja kõrge muutujad salvestavad indeksid, mis esindavad praeguse otsinguruumi piire. kesk salvestab indeksi keskele:

int madal = 0, kõrge = arr_size - 1, keskmine;

Peamine samas () silmus kitsendab otsinguruumi. Kui madala indeksi väärtus muutub kunagi suuremaks kui kõrge indeks, siis on otsinguruum ammendatud, mistõttu väärtust ei saa olla.

samal ajal (madal <= kõrge) {
/* jätkab... [1] */
 }
tagasi-1;

Pärast tsükli alguses oleva keskpunkti värskendamist on kolm võimalikku tulemust.

  1. Kui keskpunkti väärtus on see, mida otsime, tagastage see indeks.
  2. Kui keskpunkti väärtus on suurem kui otsitav väärtus, vähendage kõrget väärtust.
  3. Kui keskpunkti väärtus on väiksem, suurendage madalat väärtust. 
/* [1] ...jätkub */
 keskmine = (madal + (kõrge - madal)) / 2;
if (arr[mid] == otsingu_number)
tagasi keskmine;
muidukui (arr[kesk] > otsingu_number)
 kõrge = keskmine - 1;
muidu
 madal = keskmine + 1;

Testige funktsiooni kasutaja sisendiga. Kasutage scanf() käsurealt sisendi saamiseks, sealhulgas massiivi suuruse, sisu ja otsitava numbri saamiseks:

intpeamine(){
int arr[100], i, arr_size, search_number;
 printf("Sisestage elementide arv: ");
 scanf("%d", &arr_size);
 printf("Palun sisestage numbrid: ");
jaoks (i = 0; i < arr_size; i++) {
 scanf("%d", &arr[i]);
 }


printf("Sisesta otsitav number: ");
 scanf("%d", &otsingu_number);


i = binaarne otsing (arr, arr_size, search_number);


kui (i==-1)
 printf("Number puudub");
muidu
 printf("Number on asukohas %d", i + 1);
tagasi0;
}

Kui leiate numbri, kuvage selle asukoht või indeks, vastasel juhul kuvatakse teade, et numbrit pole.

Binaarne otsing C++ abil

Saate teisendada C-programmi C++-programmiks, importides faili Sisend-väljundvoog ja kasuta nimeruumi std et vältida selle kordamist programmi jooksul mitu korda.

#kaasa <iostream>
kasutades nimeruumstd;

Kasutage cout ekstraheerimisoperaatoriga << selle asemel printf() ja cin sisestusoperaatoriga >> selle asemel scanf() ja teie C++ programm on valmis.

printf("Sisestage elementide arv: ");
cout <<"Sisestage elementide arv: ";
scanf("%d", &arr_size);
cin >> arr_size;

Binaarne otsing Pythoni abil

Kuna Pythonil pole massiivide sisseehitatud tuge, kasutage loendeid. Määratlege funktsioon, binaarne otsing (), mis aktsepteerib kolme parameetrit, loendit, selle suurust ja otsitavat numbrit:

defbinaarne otsing(arr, arr_size, search_number):
 madal = 0
 kõrge = arr_size - 1
samal ajal madal <= kõrge:
 keskmine = madal + (kõrge-madal)//2
 if arr[mid] == otsingu_number:
tagasi kesk
elif arr[mid] > search_number:
 kõrge = keskmine - 1
muidu:
 madal = keskmine + 1
tagasi-1

Initsialiseerige kaks muutujat, madal ja kõrge, et olla loendi alumine ja ülemine piir. Sarnaselt C-rakendusega kasutage a samal ajal silmus, mis ahendab otsinguruumi. Initsialiseeri kesk loendi keskmise väärtuse salvestamiseks. Python pakub põrandajaotuse operaatorit (//), mis annab suurima võimaliku täisarvu.

Tehke võrdlused ja kitsendage otsinguruumi, kuni keskmine väärtus võrdub otsingunumbriga. Kui otsingunumbrit pole, naaseb juhtnupp -1.

arr_size = int (input("Sisestage elementide arv: "))
arr=[]
print("Palun sisestage numbrid: ", lõpp="")
i jaoks vahemikus (0,arr_size):
 arr.append(int(sisend()))
otsingu_number = int (input("Sisesta otsitav number: "))
tulemus = binaarne otsing (arr, arr_size, search_number)
kui tulemus == -1:
 print("Number puudub")
muidu:
 print ("Arv on kohal asendis ", (tulemus + 1))

Testige funktsiooni kasutaja sisendiga. Kasutage sisend() loendi suuruse, sisu ja otsitava numbri saamiseks. Kasutage int() Pythoni poolt vaikimisi aktsepteeritud stringisisendi tippimiseks täisarvuks. Numbrite loendisse lisamiseks kasutage nuppu lisa () funktsiooni.

Helistama binaarne otsing () ja andke argumendid edasi. Kui leiate numbri, kuvage selle asukoht või indeks, vastasel juhul kuvatakse teade, et numbrit pole.

Binaarse otsingu algoritmi väljund

Järgmine on binaarse otsingu algoritmi väljund, kui element on massiivis olemas:

Järgmine on binaarse otsingu algoritmi väljund, kui elementi massiivis pole:

Õppige põhilisi andmestruktuure ja algoritme

Otsing on üks esimesi algoritme, mida õpite ja seda küsitakse sageli kodeerimisvõistlustel, paigutustel ja intervjuudel. Mõned teised algoritmid, mida peaksite õppima, on sortimine, räsimine, dünaamiline programmeerimine, stringide sobitamine ja primaalsuse testimise algoritmid.

Lisaks on oluline mõista algoritmide aja ja ruumi keerukust. Need on arvutiteaduse üks olulisemaid mõisteid mis tahes algoritmi tõhususe määramisel. Andmestruktuuride ja algoritmide tundmisega olete kindlasti loonud parimad programmid.