W niektórych przypadkach czas poszukiwania możemy znacząco zmniejszyć. Dzieje się tak na przykład, gdy przeszukiwany zbiór przechowujemy w rosnąco uporządkowanej tablicy. W takim przypadku wystarczy jedynie \( O(\log n) \) operacji, by odnaleźć poszukiwany element lub stwierdzić jego brak.
Algorytm utrzymuje zakres \( [l,\ldots,r] \), w którym może znajdować się element; przy każdym porównaniu zakres zostaje zmniejszony o połowę.
function WyszukiwanieBinarne(x, A[1..n]) { zakładamy, że tablica A jest uporządkowana rosnąco } begin l:=1;r:=n; while (l<=r) do begin { niezmiennik: poszukiwany element może znajdować się w zakresie A[l..r] } m:=(l+r) div 2; if (A[m]<;x) then l:=m+1 else if (A[m]>x) then r:=m-1 else return m; { ponieważ A[m]=x } end; return brak poszukiwanego elementu; end;