11.6 S e a rching | 557{
int first = 0; // Lowest position in search area
int last = numItems-1; // Highest position in search area
int middle; // Middle position in search area
booleanfound = false;
while(last >= first && !found)
{
middle = (first + last)/2;
if (item.compareTo(listItems[middle]) == 0)
found = true;
else if(item.compareTo(listItems[middle]) < 0)
// item not in listItems[middle]..listItems[last]
last = middle – 1;
else
// item not in listItems[first]..listItems[middle]
first = middle + 1;
}
returnfound;
}
Complexity of Searching and Sorting
We introduced Big-O notation in Chapter 9 as a way of comparing the work done by different al-
gorithms. Let’s apply it to the algorithms that we’ve developed in this chapter and see how they
compare with each other. In each algorithm, we start with a list containing some number of
items,N.
In the worst case, the isTheresequential-search method scans all Ncomponents to locate an
item. That is, it requires Nsteps to execute. On average,isTheretakes roughly N/2 steps to find
an item; however, recall that in Big-O notation, we ignore constant factors (as well as lower-
order terms). Thus the method isThereis an order N—that is, an O(N)—algorithm.
What about the algorithm we presented for a sequential search in a sorted list? The number
of iterations is decreased for the case in which the item is missing from the list. However, we
have simply taken a case that would require Nsteps and reduced its time, on average, to N/2
steps. Therefore, this algorithm is also O(N).
Now consider isTherewhen we use the binary search algorithm. In the worst case, it
eliminates half of the remaining list components on each iteration. Thus the worst-case number
of iterations equals the number of times Nmust be divided by 2 to eliminate all but one value.
This number is computed by taking the logarithm, base 2, of N(written log 2 N). Here are some ex-
amples of log 2 Nfor different values of N: