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.
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.
Global variables: ascending sequence of values A.1,...,A.N
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
if A.M = V then return M; else return N + 1
last modified 8th August 2001
Copyright © 2000-2001 Vladimir Zabrodsky