4.3. Bináris keresés

Amennyiben a bemenetként adott tömb nem egyszerű, hanem az elemei között valamilyen összefüggéssel rendelkezik, a keresés algoritmusa felgyorsítható. Speciálisan, ha feltesszük, hogy T rendezett, akkor az intervallumfelezés elve alapján a keresés jelentős mértékben felgyorsítható.

Procedure BinárisKeresés(T,a) 
Input: A T rendezett tömb és a keresendő a
Eredmény: n, amelyikre T[n]=a, vagy T.hossz, ha nincs ilyen 
1  i = 0 
2  j = T.hossz-1 
3  n = T.hossz
4  while i≤=j do
5     k = floor((i+j)/2)
6     if T[k] == a then 
7        j = i-1
8        n = k
9     else 
10       if T[k]≤a then 
11          i = k+1
12       else
13          j = k-1
14       endif
15    endf
16 endw
17 Return(n)

A keresés lépései során a (j-i) értéke hozzávetőleg feleződik, ezért a legrosszabb esethez tartozó időbonyolultsága O(log(n)).