Difference between revisions 2027490 and 2028309 on bswiki

{{Siroče|23|02|2012}}
{{Preuređivanje}}
{{Standardi}}
{{Wiki}}
{{Kategorizacija}}⏎
U [[Računarstvo|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++:

{| class="wikitable" border="1"
|
* 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;
* }

|}
[[Kategorija:Računarstvo]]

[[en:Binary search algorithm]]