De ce contează?
Cauți cuvântul „pisică” într-un dicționar gros. Nu citești pagină cu pagină de la „a” — deschizi fix la mijloc. Ești la „m”: „pisică” e mai departe, așa că arunci instant toată prima jumătate. Deschizi iar la mijloc în ce a rămas, te apropii, și după câteva deschideri ai răspunsul. Funcția binary_search din STL face exact asta într-un vector sortat: îți spune dacă valoarea există, fără să caute prin tot.
Intuiția
binary_search(v.begin(), v.end(), x) îți răspunde la o singură întrebare: există x în vectorul v? Întoarce true sau false. Secretul vitezei e că nu se uită la fiecare element — se uită la cel din mijloc, vede în ce jumătate ar putea fi x, și aruncă cealaltă jumătate. Exact ca dicționarul: pentru că totul e ordonat, o singură comparație elimină jumătate din muncă. Dintr-un milion de elemente mai rămâne jumătate de milion după prima comparație, un sfert după a doua — în vreo 20 de pași ai răspunsul.