(^554) | Array-Based Lists
[first]
listItems
[middle] [last]
item
??
Figure 11.9 Binary SearchThis algorithm should make sense. With each comparison, at best, we find the item for
which we are searching; at worst, we eliminate half of the remaining list from consideration.
Before coding this algorithm, we need to determine when the search area is empty. If the
search area is between listItems[first]and listItems[last], then the area is empty if last
is less than first.
Let’s do a walk-through of the binary search algorithm. The item we are searching for is
"bat". Figure 11.10a shows the values of first,last, and middleduring the first iteration. In
this iteration,"bat"is compared with "dog", the value in listItems[middle]. Because "bat"is
less than (comes before) "dog",lastbecomes middle – 1 and firststays the same. Figure 11.10b
shows the situation during the second iteration. This time,"bat"is compared with "chicken",
the value in listItems[middle]. Because "bat"is less than (comes before) "chicken",lastbe-
comes middle – 1 and firstagain stays the same.
In the third iteration (Figure 11.10c),middleand firstare both 0. The item "bat"is com-
pared with "ant", the item in listItems[middle]. Because "bat"is greater than (comes after)
"ant",firstbecomes middle + 1. In the fourth iteration (Figure 11.10d),first,last, and mid-
dleare all the same. Again,"bat"is compared with the item in listItems[middle]. Because "bat"
is less than "cat",lastbecomes middle – 1. Now that lastis less than first, the process
stops; foundis false.
The binary search is the most complex algorithm that we have examined so far. Table
11.2 shows first,last,middle, and listItems[middle]for searches for the items "fish","snake",
and "zebra", using the same data as in the previous example. Examine the results in this table
carefully.
Notice in the table that whether we searched for"fish","snake",or"zebra", the loop never
executed more than four times. It never executes more than four times in a list of 11 components