}
==

Invariantul este <tex>A[lo] \lt x \le A[hi] </tex> (pentru simplitate consideram <tex>A[-1] = -\infty</tex> si <tex>A[A.length] = +\infty</tex>). La fiecare pas injumatatim distanta intre lo si hi. Observam ca invariantul face ca lo sa fie tot timpul diferit de hi si astfel conditia continuare e hi - lo > 1 nu hi - lo > 0. Cand hi si lo sunt consecutive putem lua o decizie, sa returnam A[hi] daca x e in sir sau -1 daca x nu apare in sir.

Invariantul este <tex>A[lo] \le x \le A[hi] </tex> (pentru simplitate consideram <tex>A[-1] = -\infty</tex> si <tex>A[A.length] = +\infty</tex>). La fiecare pas injumatatim distanta intre lo si hi. Observam ca invariantul face ca lo sa fie tot timpul diferit de hi si astfel conditia continuare e hi - lo > 1 nu hi - lo > 0. Cand hi si lo sunt consecutive putem lua o decizie, sa returnam A[hi] daca x e in sir sau -1 daca x nu apare in sir.

O data ce ati inteles ideea de mai sus, veti vedea cum puteti schimba invariantul usor pentru a rezolva probleme ca gasirea ultimei aparitii a lui x in sirul sortat, gasirea  predecesorului lui x in sir sau gasirea succesorului.