Universidad de Costa Rica
Escuela de Ciencias de la
Computación e Informática
[<=] [home] [<>] [\/] [=>]


procedure BINSRCH(F,n,i,K)
// Search an ordered sequential file F with records R1, ...,Rn and
   the keys K1K2 ≤ ... ≤ Kn for a record Ri such that Ki = K;
   i = 0 if there is no such record else Ki = K. Throughout the
   algorithm, l is the smallest index such that Kl may be K and u
   the largest index such that Ku may be K//

    l ← 1; un
    while lu do
    m(l + u)/2      //compute index of middle record//
        :K > Km: lm + 1       //look in upper half//
        :K = Km: im; return
        :K < Km: um - 1       //look in lower half//
  i ← 0    //no record with key K//
Horowitz, E.; Sahni, S.
"Fundamentals of Data Structures"; Computer Science Press; 1982.