Blog / Căutare binară algoritm eficient C++
Algoritmul de căutare binară este folosit pentru a găsi poziția unui număr dintr-un vector sortat. Atenție, acest program funcționează doar dacă tabloul unidimensional este introdus sortat crescător, în caz contrar trebuie sortat link către 3 algoritmi eficienți de sortare C++.
Cum funcționează codul prezentat?
Citim în
n
lungimea vectorului, înv
elementele sale și numărul a cărui poziție vrem să o aflămDeclarăm variabilele de parcurgere: stânga, dreapta și poziția căutată
Cât timp poziția din stânga este mai mică decât cea din dreapta executăm următoarele comenzi:
Atribuim variabilei
mijloc
media aritmetică dintre indiciistanga
drepata Verificăm dacă elementul din mijlocul vectorului este mai mare sau mai decât numărul căutat
Dacă este mai mare atribuim poziției căutate valoarea
mijloc
și pozițieidreapta
valoareamijloc - 1
În cazul în care numărul este mai mic, atribuim poziției
stanga
valoareamijloc - 1
La finalul structurii repetitive (
while
), verificăm dacă elementul căutat apare pe poziția găsită, în caz contrar acesta nu apare în vector
Implementarea C++:
Probleme recomandate:
Cautare Binara PBinfo #508 [rezolvare]
Clase PBinfo #2644 [rezolvare]
cb PBinfo #2276 [rezolvare]