BINARY SEARCH

RECURSIVE VERSION
 

function bsearch(intArray A[s..f], int X)   returns int, boolean  
   if  $f ~<~ s ~~\rightarrow$   return  FALSE 
   |  $f ~= ~s ~~\rightarrow$  
      return f, (X = A[f])  
   |  $f ~\gt ~s ~~\rightarrow$  
      mid := $\lfloor (s+f)/2 \rfloor$ 
      if $X ~\leq ~A$[mid]    $\rightarrow$  
         return bsearch(A[s..mid],  X) 
      |  X  >  A[mid]    $\rightarrow$  
         return bsearch(A[mid+1..f],  X) 
      fi
   fi 
end bsearch 

BINARY SEARCH

ITERATIVE VERSION
 

function bsearch(intArray A[s..f], int X)   returns int, boolean  
   do  $f ~\gt ~s ~~\rightarrow$
      mid := $\lfloor (s+f)/2 \rfloor$ 
      if $X ~\leq ~A$[mid]    $\rightarrow$  
         f := mid  
      |  X  >  A[mid]    $\rightarrow$  
         s := mid +1 
      fi
   od 
   if $f ~\neq~ s$    $\rightarrow$ 
      return  FALSE 
   |  $f ~= ~s ~~\rightarrow$  
      return f, (X = A[f])  
   fi  
end bsearch