48 SEARCHING AND SELECTION ALGORITHMS
loop’s conditional will become false, and the loop will stop. Therefore, the loop
does always stop.
Does this algorithm return the correct answer? If we find the target, the
answer is obviously Yes because of the return. If the middle element doesn’t
match, each pass through the loop eliminates from consideration one-half of
the remaining elements because they are all either too large or too small. As
was discussed in the previous paragraph, we will eventually get down to just
one element that must be examined.^3 If this is the key we are looking for, the
value of middle will be returned. If it is not the key we are looking for,
start will become greater than end or end will become less than start.
This means that if the target was in the list, it would be above or below the
middle value, respectively. But, based on the values of start and end, we
know that previous comparisons eliminated all of the other values, so the target
is not in the list. The loop will stop, and the function will indicate a failed
search by returning zero. So, the algorithm does return the correct answer.
Because of the halving nature of this algorithm, we will assume for our anal-
ysis that N = 2k 1 for some value of k. If this is the case, how many elements
will be left for the second pass? What about the third pass? In general, you
should see that if on some pass of the loop we have 2j 1 elements under
consideration, there are 2j^1 1 elements in the first half, 1 element in the
middle, and 2j^1 1 in the second half. Therefore, the next pass will have
2 j^1 1 elements left (for 1 ≤j≤k). This assumption will make the following
analysis easier to do, but this assumption is not necessary, as you will see in the
exercises.■ 2.2.1 Worst-Case Analysis
In paragraph above, we showed that the power of 2 is decreased by one each
pass of the loop. It was also shown that the last pass of the loop occurs when
the list has a size of 1, which occurs when j is 1 (2^1 1 = 1). This means that
there are at most k passes when N = 2k 1. Solving this equation tells us that
the worst case is k = lg(N + 1).(^3) You should also see this from the process of repeatedly doing an integer division by 2.
No matter what size list you start with, if you keep dividing by 2 (throwing away the
fractional portion), you will eventually wind up with a list of one element.