Jedan od najtemeljnijih algoritama u računalnoj znanosti je algoritam binarnog pretraživanja. Binarno pretraživanje možete implementirati pomoću dvije metode: iterativne metode i rekurzivne metode. Dok obje metode imaju istu vremensku složenost, iterativna metoda je mnogo učinkovitija u smislu prostorne složenosti.

Iterativna metoda ima prostornu složenost od O(1) u usporedbi s O (prijava) proizvedeni rekurzivnom metodom. Dakle, kako možete implementirati algoritam binarnog pretraživanja pomoću iterativne metode u C, C++ i Python?

Što je binarno pretraživanje?

Binarno pretraživanje poznato i kao poluintervalno pretraživanje, logaritamsko pretraživanje ili binarno sjeckanje algoritam je koji pretražuje i vraća položaj elementa u sortiranom nizu. Element pretraživanja uspoređuje se sa srednjim elementom. Uzimajući prosjek donje i gornje granice, možete pronaći srednje elemente.

Ako je element pretraživanja veći od srednjeg elementa, to znači da su svi elementi s lijeve strane manji od elementa pretraživanja. Dakle, kontrola se pomiče na desnu stranu niza (ako je niz u uzlaznom redoslijedu) povećanjem donje granice na sljedeću poziciju srednjeg elementa.

instagram viewer

Slično, ako je element pretraživanja manji od srednjeg elementa, to znači da su svi elementi na desnoj strani veći od elementa pretraživanja. Dakle, kontrola se pomiče u lijevi dio niza promjenom gornje granice na prethodnu poziciju srednjeg elementa.

To drastično smanjuje broj usporedbi u usporedbi s provedba linearnog pretraživanja gdje je broj usporedbi jednak broju elemenata u najgorem slučaju. Ova se metoda pokazala vrlo korisnom za pronalaženje brojeva u imeniku ili riječi u rječniku.

Ovdje je dijagramski prikaz Algoritam binarnog pretraživanja:

Binarno pretraživanje pomoću C

Slijedite ove korake za implementaciju binarnog pretraživanja koristeći C:

Cijeli izvorni kod programa binarnog pretraživanja koji koristi C, C++, Javu i Python prisutan je u ovom GitHub spremište.

Program definira funkciju, binarnopretraživanje(), koji vraća ili indeks pronađene vrijednosti ili -1 ako nije prisutan:

#uključi <stdio.h>
intbinarnoTraženje(int dolazak [], int arr_size, int broj_trage){
/*... */
}

Funkcija radi tako što iterativno sužava prostor pretraživanja. Budući da binarno pretraživanje radi na sortiranim nizovima, možete izračunati sredinu koja inače nema smisla. Od korisnika možete zatražiti sortirani niz ili upotrijebiti algoritme sortiranja kao što su Bubble ili Selection sort.

The nizak i visoka varijable pohranjuju indekse koji predstavljaju granice trenutnog prostora pretraživanja. sredina pohranjuje indeks u sredini:

int nizak = 0, visoko = arr_size - 1, sredina;

Glavni dok() petlja će suziti prostor pretraživanja. Ako vrijednost niskog indeksa ikada postane veća od visokog indeksa, tada je prostor za pretraživanje iscrpljen, tako da vrijednost ne može biti prisutna.

dok (nisko <= visoko) {
/* nastavlja se... [1] */
 }
povratak-1;

Nakon ažuriranja središnje točke na početku petlje, postoje tri moguća ishoda:

  1. Ako je vrijednost na sredini ona koju tražimo, vratite taj indeks.
  2. Ako je srednja vrijednost veća od one koju tražimo, smanjite visoku.
  3. Ako je srednja vrijednost niža, povećajte nisku. 
/* [1] ...nastavak */
 srednji = (nisko + (visoko - nisko)) / 2;
if (arr[mid] == search_number)
povratak sredina;
drugoako (arr[mid] > search_number)
 visoko = srednje - 1;
drugo
 nisko = srednje + 1;

Testirajte funkciju korisničkim unosom. Koristiti scanf() da dobijete unos iz naredbenog retka, uključujući veličinu polja, njegov sadržaj i broj za pretraživanje:

intglavni(){
int dolazak [100], i, arr_size, search_number;
 printf("Unesite broj elemenata: ");
 scanf("%d", &arr_veličina);
 printf("Molimo unesite brojeve: ");
za (i = 0; ja < arr_veličina; i++) {
 scanf("%d", &arr[i]);
 }


printf("Unesite broj za pretragu: ");
 scanf("%d", &broj_trage);


i = binarnoTraženje (arr, arr_size, search_number);


ako (i==-1)
 printf("Broj nije prisutan");
drugo
 printf("Broj je prisutan na poziciji %d", i + 1);
povratak0;
}

Ako pronađete broj, prikažite njegovu poziciju ili indeks, inače se prikazuje poruka da broj nije prisutan.

Binarno pretraživanje pomoću C++

Možete pretvoriti C program u C++ program uvozom Ulazni izlazni tok i koristiti imenski prostor std kako biste izbjegli ponavljanje više puta tijekom programa.

#uključi <iostream>
korištenjem imenski prostorstd;

Koristiti cout s operaterom ekstrakcije << umjesto printf() i cin s operatorom umetanja >> umjesto scanf() i vaš C++ program je spreman.

printf("Unesite broj elemenata: ");
cout <<"Unesite broj elemenata: ";
scanf("%d", &arr_veličina);
cin >> arr_veličina;

Binarno pretraživanje pomoću Pythona

Budući da Python nema ugrađenu podršku za nizove, koristite popise. Definirajte funkciju, binarnopretraživanje(), koji prihvaća tri parametra, popis, njegovu veličinu i broj za pretraživanje:

defbinarnoTraženje(arr, arr_size, search_number):
 nisko = 0
 visoko = arr_size - 1
dok nizak <= visok:
 srednje = nisko + (visoko-nisko)//2
 if arr[mid] == search_number:
povratak sredina
elif arr[mid] > search_number:
 visoko = srednje - 1
drugo:
 nisko = srednje + 1
povratak-1

Inicijalizirati dvije varijable, nizak i visoka, da služi kao donja i gornja granica popisa. Slično C implementaciji, koristite a dok petlja koja sužava prostor pretraživanja. Inicijalizirati sredina za pohranjivanje srednje vrijednosti popisa. Python pruža operator podjele (//) koji daje najveći mogući cijeli broj.

Napravite usporedbe i suzite prostor pretraživanja dok srednja vrijednost ne bude jednaka broju pretraživanja. Ako traženi broj nije prisutan, kontrola će se vratiti -1.

arr_size = int (ulaz("Unesite broj elemenata: "))
arr=[]
ispis("Molimo unesite brojeve: ", kraj="")
za i u rasponu (0,arr_size):
 arr.dodaj(int(ulazni()))
broj_trage = int (unos("Unesite broj za pretragu: "))
rezultat = binarnopretraživanje (arr, arr_size, search_number)
ako je rezultat == -1:
 ispis("Broj nije prisutan")
drugo:
 print("Broj je prisutan na poziciji ", (rezultat + 1))

Testirajte funkciju korisničkim unosom. Koristiti ulazni() da biste dobili veličinu popisa, njegov sadržaj i broj za pretraživanje. Koristiti int() za tipiziranje unosa niza koji prihvaća Python kao zadani u cijeli broj. Za dodavanje brojeva na popis koristite dodati() funkcija.

Poziv binarnopretraživanje() i proći argumente. Ako pronađete broj, prikažite njegovu poziciju ili indeks, inače se prikazuje poruka da broj nije prisutan.

Izlaz algoritma binarnog pretraživanja

Sljedeći je rezultat algoritma binarnog pretraživanja kada je element prisutan u nizu:

Sljedeći je rezultat algoritma binarnog pretraživanja kada element nije prisutan u nizu:

Naučite temeljne strukture podataka i algoritme

Pretraživanje je jedan od prvih algoritama koje naučite i koji se često postavljaju na natjecanjima u kodiranju, postavljanjima i intervjuima. Neki drugi algoritmi koje biste trebali naučiti su sortiranje, raspršivanje, dinamičko programiranje, podudaranje nizova i algoritmi za testiranje primarnosti.

Dodatno, bitno je razumjeti vremensku i prostornu složenost algoritama. Oni su jedan od najvažnijih koncepata u računalnoj znanosti u određivanju učinkovitosti bilo kojeg algoritma. Uz poznavanje struktura podataka i algoritama, dužni ste izgraditi najbolje programe.