Binarno pretraživanje

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; }