Wyszukiwanie binarne

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;