This is a slight variation on a specification of iterative binary search due to Bentley and is from column four of Programming Pearls (Addison-Wesley 1986).
We are to determine whether the sorted array X[1..N] contains the element T. We calculate P, the position of T in X. When P is zero, T is not in X[1..N]. Otherwise, 1<=P<=N and T=X[P].
We know that N>gt;=0 and that X[1] <= X[2] <= ... <= X[N]. When N=0 the array is empty. The types of T and the elements of X are the same.
Binary search solves the problem by keeping track of a range within the array in which T must be if it is anywhere in the array. Initially, the range is the entire array. The range is shrunk by comparing its middle element to to T and discarding half the arrange. The process continues until T is discovered in the array or until the range in which it must lie is known to be empty.
Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.
Source text last modified Mon Nov 10 08:57:45 1997.
This page generated on Mon Nov 10 10:13:01 1997 by SiteWeaver.
Contact our webmaster at rebelsky@math.grin.edu