Binarno iskanje
Iz Wikipedije, proste enciklopedije
Binarno iskanje je algoritem za iskanje ključa v urejeni polju podatkov. Iskanje poteka tako, da se pri vsakem noven povpraševanju izloči polovico podatkov.
Primer binarnega iskanja: zamislimo si neko naključno število in prijatelju rečemo, naj jo ugiba. Povemo mu, da je to število med 1 in 50. Prijatelj bo nato spraševal: "Ali je večje od 20?" in mi mu rečemo da. Prijatelj bo sedaj vedel da mora ugibati število, ki je nad 20, zato bo vse tiste, ki so manjše izločil. Če rečemo, da je število manjše od 35 bo vedel, da mora izločiti vsa števila nad 34. To se nadaljuje tako dolgo, dokler končno ne najde števila.
[uredi] Psevdokoda
while (levi <= desni) {
sredina = zaokrozi((levi+desni) / 2);
if (kljuc > a[sredina])
levi = sredina + 1;
else if (kljuc < a[sredina])
desni = sredina - 1;
else
return sredina;
}
return -1; /* kljuc ni najden. */
Podobno deluje binarno iskanje, z izločanjem. Binarno iskanje je logaritmični algoritem in ima čas O(log n).
 |
Ta članek, ki se nanaša na računalništvo je škrbina. Pomagaj Wikipediji in ga razširi. |
