Algorithm analysis - Data Structures and Problem Solving Using Java - page 209

figure 5.11
Basic binary search
that uses three-way
comparisons

1 /**
2 * Performs the standard binary search
3 * using two comparisons per level.
4 * @return index where item is found, or NOT_FOUND.
5 */
6 public static <AnyType extends Comparable<? super AnyType>>
7 int binarySearch( AnyType [ ] a, AnyType x )
8 {
9 int low = 0;
10 int high = a.length - 1;
11 int mid;
12
13 while( low <= high )
14 {
15 mid = ( low + high ) / 2;
16
17 if( a[ mid ].compareTo( x ) < 0 )
18 low = mid + 1;
19 else if( a[ mid ].compareTo( x ) > 0 )
20 high = mid - 1;
21 else
22 return mid;
23 }
24
25 return NOT_FOUND; // NOT_FOUND = -1
26 }

The mathematics involves computing the weighted average by calculating the
sum of a finite series. The bottom line, however, is that the running time for each
search is . In Exercise 5.26, you are asked to complete the calculation.
For reasonably large values of N , the binary search outperforms the sequen-
tial search. For instance, if N is 1,000, then on average a successful sequential
search requires about 500 comparisons. The average binary search, using the
previous formula, requires , or eight iterations for a successful
search. Each iteration uses 1.5 comparisons on average (sometimes 1; other
times, 2), so the total is 12 comparisons for a successful search. The binary
search wins by even more in the worst case or when searches are unsuccessful.

O (log N )

log N - 1

If we want to make the binary search even faster, we need to make the
inner loop tighter. A possible strategy is to remove the (implicit) test for a suc-
cessful search from that inner loop and shrink the range down to one item in
all cases. Then we can use a single test outside of the loop to determine if the
item is in the array or cannot be found, as shown in Figure 5.12. If the item we
are searching for in Figure 5.12 is not larger than the item in the mid position,
then it is in the range that includes the mid position. When we break the loop,
the subrange is 1, and we can test to see whether we have a match.

Optimizing the
binary search can
cut the number of
comparisons
roughly in half.