Java Reference
In-Depth Information
if
(found)
return
mid;
else
return
-1;
}
//end binarySearch
Note that in the binary search algorithm, two key (item) comparisons are made each time
through the loop, except in the successful case the last time through the loop, when only
one key comparison is made.
Next, we do a walk-through of the binary search algorithm on the list shown in
Figure 14-15.
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]
list
4
8 19 25 34 39 45 48 66 75 89 95
FIGURE 14-15
Sorted list for binary search
The size of the list in Figure 14-15 is
12
, that is,
listLength = 12
. Suppose that the item
for which we are searching is
89
, that is,
searchItem = 89
. Before the
while
loop
executes,
first = 0
,
last = 11
, and
found =
false
. In the following, 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
6
11
8
66
2
3
9
11
10
89
1 (found is
true
)
The item is found at location
10
and the total number of key comparisons is
5
.
Next, let's search the list for
34
, that is,
searchItem = 34
. 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
1
4
2
0
4
2
19
2
3
3
4
3
25
2
4
4
4
4
34
1 (found is
true
)
The item is found at location
4
and the total number of key comparisons is
7
.
Search WWH ::
Custom Search