BINARY SEARCH

PROBLEM
Given an ascending sequence of values A.1,...,A.N and target value V. Search routine should return an index of V in A. if V is present in the array, and N+1 otherwise.

ALGORITHMS
Divide the array into two parts, determine which of the two parts the key being sought belongs to, then concentrate on that part ... The total number of comparisons is only about lgN.

IMPLEMENTATION
Unit: internal function
 
Global variables: ascending sequence of values A.1,...,A.N
 
Parameters: positive integer N, arbitrary value V
 
Returns: the index of V in A. if V is present in the array, and N+1 otherwise

 


BINARY_SEARCH: procedure expose A.
parse arg N, V
L = 1; R = N
do while L <= R
  M = (L + R) % 2
  if V = A.M then leave
  if V < A.M then R = M - 1; else L = M + 1
end
if A.M = V then return M; else return N + 1

 

CONNECTIONS


cover contents index main page

last modified 8th August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic.

mail