Java Reference
In-Depth Information
Let's now search for
22
, that is,
searchItem = 22
. Before the
while
loop executes,
first = 0
,
last = 11
, and
found =
false
. In the following, as before, we trace the
execution of the
while
loop, showing the values of
first
,
last
, and
mid
, and the
number of key comparisons during each iteration:
Iteration
first
last
mid
list[mid]
Number of key comparisons
1
0
11
5
39
2
2
0
4
2
19
2
3
3
4
3
25
2
4
3
2
the loop stops (because first > last) unsuccessful search
This is an unsuccessful search. The total number of key comparisons is
6
.
From these tracings of the binary search algorithm, you can see that every time you go
through the loop, you cut the size of the sublist by half. That is, the size of the sublist you
search the next time through the loop is half the size of the previous sublist.
PERFORMANCE OF THE BINARY SEARCH
Suppose that L is a sorted list of size 1024 and we want to determine if an item x is in L.
From the binary search algorithm, it follows that every iteration of the
while
loop cuts
the size of the search list by half. (For example, see Figures 14-13 and 14-14.) Because
1024
¼
2
10
, the
while
loop will have, at most, 11 iterations to determine whether x is in
L. (Note that the symbol
means approximately equal to.) Because every iteration of the
while
loop makes two item (key) comparisons, that is, x is compared twice with the
elements of L, the binary search will make, at most, 22 comparisons to determine
whether x is in L. On the other hand, recall that a sequential search on average will
make 512 comparisons to determine whether x is in L.
To better understand how fast binary search is compared to sequential search, suppose
that L is of size 1048576. Because 1048576
¼
2
20
,itfollowsthatthe
while
loop in
binary search will have at most 21 iterations to determine whether an element is in L.
Every iteration of the
while
loop makes two key (that is, item) comparisons. There-
fore, to determine whether an element is in L, binary search makes at most 42 item
comparisons. On the other hand, on average, a sequential search will make 524,288
key (item) comparisons to determine whether an element is in L.(Becauseatelephone
book is in alphabetical order, it can be searched using a binary search. For example, to
search for ''Smith,'' you open the telephone book in the middle to start the search.)
In general, if L is a sorted list of size n, to determine whether an element is in L, the
binary search makes at most 2log
2
n + 2 key (item) comparisons.
Search WWH ::
Custom Search