De ce contează?
Reglezi un termostat căruia nu îi vezi temperatura — doar un bec: verde dacă e destul de cald, roșu dacă nu. Nu încerci toate gradele la rând. Pui un grad la mijloc: dacă becul e verde, știi că toate gradele mai mari sunt și ele verzi, deci pragul căutat e mai jos; dacă e roșu, e mai sus. Becul nu îți spune niciodată direct răspunsul — dar la fiecare apăsare îți spune în ce jumătate stă. În câțiva pași ai prins exact gradul de la care se aprinde verdele, fără să fi văzut vreodată temperatura.
Ideea-cheie
Până acum ai căutat binar o valoare într-un vector sortat. Dar uneori nu cauți un element — cauți un număr (un timp, o capacitate, o lungime) care e cel mai mic (sau cel mai mare) ce „merge”. Vectorul lipsește; spațiul în care cauți e chiar intervalul de răspunsuri posibile.
Trucul: în loc să ai elementele ordonate, ai o funcție de verificare fezabil(x) care întoarce „da” sau „nu” — și care e monotonă. Dacă fezabil(x) e adevărat, atunci e adevărat și pentru orice valoare mai relaxată; din momentul în care devine adevărat, rămâne adevărat. Răspunsurile arată deci ca un șir de „nu nu nu da da da” — exact ca becul roșu apoi verde.
Dacă „merge la pragul x” implică automat „merge la orice prag mai mare decât x”, atunci răspunsurile formează un șir ordonat de nu-uri urmate de da-uri. Răspunsul corect stă fix pe graniță — primul „da”. Iar o graniță într-un șir ordonat se găsește prin căutare binară. Nu ai nevoie de un vector real: predicatul monoton fezabil(x) ține locul sortării, iar tu cauți binar granița lui.