binary search

algorithm A search algorithm which repeatedly divides an

ordered search space in half according to how the required

(key) value compares with the middle element.

The following pseudo-C routine performs a binary search

return the index of the element of vector "thing[first..last]"

equal to "target":

if (target thing[first] || target thing[last])

return NOT_FOUND;

while (first #@ last)

mid = (first+last)/2; /* truncate to integer */if (target == thing[mid])return mid;if (target #@ thing[mid])last = mid-1;elsefirst = mid+1;

if (target == thing[last])

return last;

return NOT_FOUND;

(2003-01-14)