2.2 BINARY SEARCH 47what is left of the list with each comparison. This results in the following
algorithm:^2
BinarySearch( list, target, N )
list the elements to be searched
target the value being searched for
N the number of elements in the list
start = 1
end = N
while start ≤ end do
middle = (start + end) / 2
select (Compare(list[middle], target)) from
case -1:start = middle + 1
case 0:return middle
case 1:end = middle - 1
end select
end while
return 0
In this algorithm, start gets reset to 1 larger than the middle when we know
that the target is larger than the element at the middle location. End gets reset
to 1 smaller than the middle when we know that the target is smaller than the
element at the middle location. These are shifted by 1 because we know by the
three-way comparison that the middle value is not equal and so can be elimi-
nated from consideration.
Does this loop always stop? If we find the target, the answer is obviously Yes,
because of the return. If we don’t find a match, each pass through the loop will
either increase the value of start or decrease the value of end. This means
that they will continue to get closer to each other. Eventually, they will
become equal to each other, and the loop will be done one more time, with
start = end = middle. After this pass (assuming that this is not the element
we are looking for), either start will be 1 greater than middle and end, o r
end will be 1 less than middle and start. In both of these cases, the while
(^2) The function Compare(x,y) is defined in Exercise 1 of Section 2.1.3. As was men-
tioned in that exercise, this function will return 1, 0, or 1, depending on whether x
is less than, equal to, or greater than y, respectively. When analyzing an algorithm that
uses Compare, it is counted as just one comparison.