De ce contează?
Doi căutători stau la cele două capete ale unei poteci drepte și ordonate și pornesc unul spre celălalt, vrând ca pașii dintre ei să însumeze exact un număr dat. Dacă suma e prea mare, cel din dreapta se retrage un pas; dacă e prea mică, cel din stânga înaintează. Pentru că poteca e ordonată, fiecare mișcare îi apropie sigur de răspuns — niciunul nu se întoarce vreodată din drum.
Intuiția
Ai un vector sortat crescător și vrei să găsești două elemente care adunate
dau un target. În loc să încerci toate perechile, pui un deget la începutul
vectorului (st) și unul la sfârșit (dr). Te uiți la suma v[st] + v[dr]:
dacă e prea mare, tragi degetul drept spre stânga; dacă e prea mică, împingi
degetul stâng spre dreapta. Sortarea face ca fiecare mișcare să fie sigură.
Pe un vector sortat crescător, suma celor doi pointeri îți spune singură
direcția: e cel mai mic candidat posibil când dr e la capăt și cel mai mare
când st e la capăt. Dacă suma e prea mare, orice altă alegere în dreapta e mai
mică, deci dr--; dacă e prea mică, orice altă alegere în stânga e mai mare,
deci st++. Nu trebuie să încerci nimic — citești direcția din sumă.