}
==

Invariantul este A[lo] < x <= A[hi] (pentru simplitate consideram A[-1] == -oo si A[A.length] == +oo). 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] < x <= A[hi] </tex> (pentru simplitate consideram <tex>A[-1] == -oo</tex> si <tex>A[A.length] == +oo</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.