Java Reference
In-Depth Information
Position
0
1
2
3
4
5
6
7
8
9
10
11 12
13
14
15
Key
11 13
21
26
29
36
40
41
45
51
54
56
65
72
77
83
Figure3.4
An illustration of binary search on a sorted array of 16 positions.
Consider a search for the position with value K = 45. Binary search first checks
the value at position 7. Because 41 < K, the desired value cannot appear in any
position below 7 in the array. Next, binary search checks the value at position 11.
Because 56 > K, the desired value (if it exists) must be between positions 7
and 11. Position 9 is checked next. Again, its value is too great. The final search
is at position 8, which contains the desired value. Thus, function
binary
returns
position 8. Alternatively, if K were 44, then the same series of record accesses
would be made. After checking position 8,
binary
would return a value of n,
indicating that the search is unsuccessful.
The final example of algorithm analysis for this section will compare two algo-
rithms for performing search in an array. Earlier, we determined that the running
time for sequential search on an array where the search value K is equally likely
to appear in any location is (n) in both the average and worst cases. We would
like to compare this running time to that required to perform a binary search on
an array whose values are stored in order from lowest to highest.
Binary search begins by examining the value in the middle position of the ar-
ray; call this position mid and the corresponding value k
mid
. If k
mid
= K, then
processing can stop immediately. This is unlikely to be the case, however. Fortu-
nately, knowing the middle value provides useful information that can help guide
the search process. In particular, if k
mid
> K, then you know that the value K
cannot appear in the array at any position greater than mid. Thus, you can elim-
inate future search in the upper half of the array. Conversely, if k
mid
< K, then
you know that you can ignore all positions in the array less than mid. Either way,
half of the positions are eliminated from further consideration. Binary search next
looks at the middle position in that part of the array where value K may exist. The
value at this position again allows us to eliminate half of the remaining positions
from consideration. This process repeats until either the desired value is found, or
there are no positions remaining in the array that might contain the value K. Fig-
ure 3.4 illustrates the binary search method. Figure 3.5 shows an implementation
for binary search.
To find the cost of this algorithm in the worst case, we can model the running
time as a recurrence and then find the closed-form solution. Each recursive call
to
binary
cuts the size of the array approximately in half, so we can model the
worst-case cost as follows, assuming for simplicity that n is a power of two.
T(n) = T(n=2) + 1 for n > 1;
T(1) = 1:
