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
