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

1 /**
2 * Performs the standard binary search
3 * using one comparison 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 if( a.length == 0 )
10 return NOT_FOUND;
11
12 int low = 0;
13 int high = a.length - 1;
14 int mid;
15
16 while( low < high )
17 {
18 mid = ( low + high ) / 2;
19
20 if( a[ mid ].compareTo( x ) < 0 )
21 low = mid + 1;
22 else
23 high = mid;
24 }
25
26 if( a[ low ].compareTo( x ) == 0 )
27 return low;
28
29 return NOT_FOUND;
30 }

figure 5.12
Binary search using
two-way comparisons

⎤
because we always shrink the range in half, possibly by rounding down. Thus,
the number of comparisons used is always

In the revised algorithm, the number of iterations is always ⎡ log N

.
Binary search is surprisingly tricky to code. Exercise 5.9 illustrates some
common errors.
Notice that for small N , such as values smaller than 6, the binary search might
not be worth using. It uses roughly the same number of comparisons for a typical
successful search, but it has the overhead of line 18 in each iteration. Indeed, the
last few iterations of the binary search progress slowly. One can adopt a hybrid
strategy in which the binary search loop terminates when the range is small and
applies a sequential scan to finish. Similarly, people search a phone book nonse-
quentially. Once they have narrowed the range to a column, they perform a
sequential scan. The scan of a telephone book is not sequential, but it also is not a
binary search. Instead it is more like the algorithm discussed in the next section.

⎡ log N ⎤ + 1