De ce contează?
Imaginează-ți o balanță cu două talere, ținută în echilibru perfect. Cât timp pui aceeași greutate în stânga și în dreapta, sau muți simetric dintr-un taler în celălalt, acul rămâne fix la mijloc — oricâte mutări ai face. Nu trebuie să urmărești fiecare mutare ca să știi unde stă acul: echilibrul este ceva care pur și simplu NU se schimbă. În algoritmică, acel „ceva care rămâne adevărat după fiecare pas" se numește invariant — și e cheia prin care înțelegi de ce un algoritm e corect, fără să-l urmărești până la capăt.
Tiparul
Un algoritm e un proces cu pași: la fiecare pas modifică o stare (un interval, un vector, o sumă). Tentația e să urmărești fiecare pas pe rând până la final. Dar de multe ori nu drumul contează, ci o proprietate care rămâne adevărată la fiecare pas — un invariant. Dacă o găsești, poți demonstra corectitudinea sau citi răspunsul direct, fără să simulezi tot.
Declanșatorul de antrenat: când vezi un proces cu pași, întreabă-te ce rămâne neschimbat la fiecare pas. Acel lucru constant este invariantul — busola care îți spune unde ajungi fără să parcurgi tot drumul.
La căutarea binară cauți o valoare x într-un vector sortat. La fiecare pas compari x cu elementul din mijloc și arunci jumătate din interval, păstrând doar capetele st si dr. Cum demonstrezi cel mai bine că algoritmul gaseste x daca x exista, fără să urmaresti toate cele aproximativ log n injumatatiri, pentru ORICE intrare posibila?
Oprește-te. Care e observația care face naivul să devină rapid? Formuleaz-o în gând, apoi verifică.