De ce contează?
Mă gândesc la un număr între 1 și 100, iar tu trebuie să-l ghicești. La fiecare încercare îți spun doar „mai mare” sau „mai mic”. Nu începi de la 1 și urci unul câte unul — spui „50”. Dacă îți zic „mai mare”, arunci instant jumătatea de jos și încerci „75”. Fiecare răspuns taie jumătate din variante, așa că în cel mult 7 întrebări nimerești numărul. Exact asta face căutarea binară pe un vector sortat: fiecare comparație elimină o jumătate.
Intuiția
Ai un vector sortat crescător și vrei să afli dacă o valoare se găsește în el. Te uiți la elementul din mijloc: dacă e prea mic, valoarea căutată e sigur în jumătatea din dreapta; dacă e prea mare, e în stânga. Într-o singură comparație arunci jumătate din vector. Repeți pe jumătatea rămasă până dai de valoare sau nu mai rămâne nimic.
Toată corectitudinea stă pe un invariant: dacă valoarea există în vector, ea se află mereu în intervalul de indici [st, dr]. La început st = 0, dr = n - 1, deci poate fi oriunde. Fiecare comparație elimină jumătatea în care valoarea sigur nu e, fără să încalce invariantul. Mijlocul îl calculezi cu mid = st + (dr - st) / 2, nu cu (st + dr) / 2: dacă st și dr sunt amândoi foarte mari, suma lor depășește int, dar diferența dr - st nu.