Eden najbolj temeljnih algoritmov v računalništvu je algoritem binarnega iskanja. Binarno iskanje lahko implementirate z dvema metodama: iterativno in rekurzivno metodo. Medtem ko imata obe metodi enako časovno kompleksnost, je iterativna metoda veliko bolj učinkovita z vidika kompleksnosti prostora.
Iterativna metoda ima prostorsko kompleksnost O(1) v primerjavi z O (prijava) izdelana po rekurzivni metodi. Torej, kako lahko implementirate algoritem binarnega iskanja z uporabo iterativne metode v C, C++ in Python?
Kaj je binarno iskanje?
Binarno iskanje, znano tudi kot polintervalno iskanje, logaritemsko iskanje ali binarno sekanje, je algoritem, ki išče in vrne položaj elementa v razvrščeni matriki. Iskalni element se primerja s srednjim elementom. Če vzamete povprečje spodnje in zgornje meje, lahko najdete srednje elemente.
Če je iskalni element večji od srednjega elementa, to pomeni, da so vsi elementi na levi strani manjši od iskalnega elementa. Torej se kontrolnik premakne na desno stran matrike (če je matrika v naraščajočem vrstnem redu) s povečanjem spodnje meje na naslednji položaj srednjega elementa.
Podobno, če je iskalni element manjši od srednjega elementa, to pomeni, da so vsi elementi na desni strani večji od iskalnega elementa. Torej se nadzor premakne na levi del matrike s spremembo zgornje meje na prejšnji položaj srednjega elementa.
To drastično zmanjša število primerjav v primerjavi z izvajanje linearnega iskanja kjer je število primerjav enako številu elementov v najslabšem možnem scenariju. Ta metoda se je izkazala za zelo uporabno za iskanje številk v imeniku ali besed v slovarju.
Tukaj je diagramski prikaz Algoritem binarnega iskanja:
Binarno iskanje s C
Sledite tem korakom za implementacijo binarnega iskanja s C:
Celotna izvorna koda binarnega iskalnega programa, ki uporablja C, C++, Javo in Python, je prisotna v tem Repozitorij GitHub.
Program definira funkcijo, binarySearch(), ki vrne bodisi indeks najdene vrednosti oz -1 če ni prisoten:
#vključi <stdio.h>
intbinarySearch(int arr[], int arr_size, int iskalna_številka){
/*... */
}
Funkcija deluje tako, da iterativno oži iskalni prostor. Ker binarno iskanje deluje na razvrščenih nizih, lahko izračunate sredino, kar sicer nima smisla. Uporabnika lahko prosite za razvrščeno matriko ali pa uporabite algoritme za razvrščanje, kot sta Bubble ali Selection sort.
The nizka in visoka spremenljivke shranijo indekse, ki predstavljajo meje trenutnega iskalnega prostora. sredina shrani indeks na sredini:
int nizko = 0, visoko = arr_size - 1, sredina;Glavni medtem() zanka bo zožila iskalni prostor. Če vrednost nizkega indeksa kdaj postane večja od visokega indeksa, je iskalni prostor izčrpan, zato vrednost ne more biti prisotna.
medtem (nizko <= visoko) {
/* nadaljuje... [1] */
}
vrnitev-1;
Po posodobitvi sredine na začetku zanke so možni trije rezultati:
- Če je vrednost na sredini tista, ki jo iščemo, vrnite ta indeks.
- Če je srednja vrednost večja od tiste, ki jo iščemo, znižajte visoko.
- Če je srednja vrednost manjša, zvišajte nizko.
/* [1] ...nadaljevanje */
srednji = (nizko + (visoko - nizko)) / 2;
if (arr[mid] == search_number)
vrnitev sredina;
drugačeče (arr[mid] > search_number)
visoko = srednje - 1;
drugače
nizka = srednja + 1;
Preizkusite funkcijo z uporabniškim vnosom. Uporaba scanf() da dobite vnos iz ukazne vrstice, vključno z velikostjo matrike, njeno vsebino in številko za iskanje:
intglavni(){
int arr [100], i, arr_size, search_number;
printf("Vnesite število elementov: ");
scanf("%d", &arr_size);
printf("Prosimo vnesite številke: ");za (i = 0; jaz < arr_size; i++) {
scanf("%d", &arr[i]);
}printf("Vnesite številko za iskanje: ");
scanf("%d", &iskalna_številka);i = binarno iskanje (arr, arr_size, search_number);
če (i==-1)
printf("Številka ni prisotna");
drugače
printf("Številka je prisotna na položaju %d", i + 1);
vrnitev0;
}
Če najdete številko, prikažite njen položaj ali indeks, sicer se prikaže sporočilo, da številke ni.
Binarno iskanje z uporabo C++
Program C lahko pretvorite v program C++ z uvozom Vhodni izhodni tok in uporaba imenskega prostora std da se izognete večkratnemu ponavljanju v celotnem programu.
#vključi <iostream>
uporabo imenski prostorstd;Uporaba cout z operaterjem ekstrakcije << namesto printf() in cin z operatorjem vstavljanja >> namesto scanf() in vaš program C++ je pripravljen.
printf("Vnesite število elementov: ");
cout <<"Vnesite število elementov: ";
scanf("%d", &arr_size);
cin >> arr_size;Binarno iskanje z uporabo Pythona
Ker Python nima vgrajene podpore za polja, uporabite sezname. Definirajte funkcijo, binarySearch(), ki sprejme tri parametre, seznam, njegovo velikost in številko za iskanje:
defbinarySearch(arr, arr_size, search_number):
nizko = 0
visoko = arr_size - 1
medtem nizko <= visoko:
srednji = nizek + (visoko-nizko)//2
if arr[mid] == search_number:
vrnitev sredina
elif arr[mid] > search_number:
visoko = srednje - 1
drugače:
nizka = srednja + 1
vrnitev-1Inicializirajte dve spremenljivki, nizka in visoka, ki služi kot spodnja in zgornja meja seznama. Podobno kot pri izvedbi C uporabite a medtem zanka, ki zoži iskalni prostor. Inicializiraj sredina za shranjevanje srednje vrednosti seznama. Python nudi operator deljenja tal (//), ki zagotavlja največje možno celo število.
Naredite primerjave in zožite iskalni prostor, dokler se srednja vrednost ne izenači z iskalnim številom. Če iskalna številka ni prisotna, se bo kontrolnik vrnil -1.
arr_size = int (vhod("Vnesite število elementov: "))
arr=[]
natisni("Prosimo vnesite številke: ", konec="")
za i v območju (0,arr_size):
arr.append(int(vnos()))
iskalno_število = int (vhod("Vnesite številko za iskanje: "))
rezultat = binarno iskanje (arr, arr_size, search_number)
če je rezultat == -1:
natisni("Številka ni prisotna")
drugače:
print("Število je prisoten na položaju ", (rezultat + 1))Preizkusite funkcijo z uporabniškim vnosom. Uporaba vnos() da dobite velikost seznama, njegovo vsebino in številko za iskanje. Uporaba int() za pretvorbo vnosa niza, ki ga Python sprejme kot privzetega, v celo število. Če želite dodati številke na seznam, uporabite pripni() funkcijo.
Pokliči binarySearch() in posredujte argumente. Če najdete številko, prikažite njen položaj ali indeks, sicer se prikaže sporočilo, da številke ni.
Izhod algoritma binarnega iskanja
Sledi rezultat algoritma binarnega iskanja, ko je element prisoten v matriki:
Sledi rezultat algoritma binarnega iskanja, ko element ni prisoten v matriki:
Naučite se temeljnih podatkovnih struktur in algoritmov
Iskanje je eden prvih algoritmov, ki se ga naučite in se ga pogosto vpraša na tekmovanjih v kodiranju, umestitvah in intervjujih. Nekaj drugih algoritmov, ki bi se jih morali naučiti, so algoritmi za razvrščanje, zgoščevanje, dinamično programiranje, ujemanje nizov in algoritmi za testiranje primalnosti.
Poleg tega je bistveno razumeti časovno in prostorsko kompleksnost algoritmov. So eden najpomembnejših konceptov v računalništvu pri določanju učinkovitosti katerega koli algoritma. Z poznavanjem podatkovnih struktur in algoritmov boste zagotovo sestavili najboljše programe.
