Binarno pretraživanje

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web stranice ili drugi izvori).
Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci, te nakon toga možete ukloniti ovaj šablon.
Wiki letter w.svg Ovaj članak je siroče zato što nema ili vrlo malo ima drugih članaka koji linkuju ovamo.
Molimo Vas da postavite linkove prema ovoj stranici sa srodnih članaka(23-02-2012)
Preferences-system.svg Ovom članku je potrebna jezička standardizacija, preuređivanje ili reorganizacija.
Pogledajte kako poboljšati članak, kliknite na link uredi i doradite članak vodeći računa o standardima Wikipedije.
Crystal Clear action spellcheck.png Moguće je da ovaj članak ne poštuje standarde Wikipedije na bosanskom jeziku
kao što su upotreba afrikata, pravopis, pisanje riječi u skladu sa standardima, te način pisanja članaka.
Wikitext.svg Ovom članku ili dijelu članka nedostaju interni linkovi.
Nakon dodavanja internih linkova uklonite ovaj šablon.

U računarskoj nauci, binarno pretraživanje je algoritam za lociranje pozicije neke stavke, u sortiranom nizu.

Binarno pretraživanje je dihotomni, "podijeli pa savladaj", pretraživački algoritam.

U svakodnevnom životu se sa ovom vrstom pretraživanja susrećeme u igri pogađanja brojeva: osoba A zamišlja neki broj, a osoba B "pogađa", tako što kaže neki broj, i dobija odgovore: "više", "manje" ili "tačno". Osoba koja nastoji da otkrije broj se u svojim pokušajima rukovodi prema dobivenim odgovorima.

Ideja je jednostavna, a uvjet da bi se primijenio algoritam za binarno pretraživanje, je da lista treba biti sortirana.

Ukratko, binarno pretraživanje možemo opisati na slijedeći način:

  • pronalazimo centralni element
  • odbacimo polovicu liste
  • pretražujemo drugu polovicu
  • nastavljamo dok se traženi element ne pronađe ili dok ne ostane niti jedan element za pretraživanje.

Funkcija binarnog pretraživanja u c++:

  • int main(){
  • const int arraySize = 10;
  • int target;
  • int Element[arraySize] = {1, 4, 6, 9, 13, 17, 20, 28, 32, 41};
  • int bottom, middle, top;
  • cout << "Unesite cilj koji trazite: ";
  • cin >> target;
  • //binarno pretrazivanje
  • bottom = 0;
  • top = 9;
  • while(top > bottom){
  • middle = (top+bottom)/2;
  • if (Element[middle] < target)
  • bottom = middle+1;
  • else
  • top = middle;
  • }
  • if (Element[top] == target)
  • cout << "Cilj je pronadjen na lokaciji " << top+1 <<"."<< endl;
  • else
  • cout << "Cilj nije pronadjen." << endl;
  • return 0;
  • }