Java Reference
In-Depth Information
The complete program is given in ListingĀ 7.7.
L
ISTING
7.7
BinarySearch.java
1
public class
BinarySearch {
2
/** Use binary search to find the key in the list */
3
public static int
binarySearch(
int
[] list,
int
key) {
4
int
low =
0
;
5
int
high = list.length -
1
;
6
7
while
(high >= low) {
8
int
mid = (low + high) /
2
;
9
if
(key < list[mid])
10 high = mid -
1
;
11
else if
(key == list[mid])
12
return
mid;
13
else
14 low = mid +
1
;
15
first half
second half
}
16
17
return
-low -
1
;
// Now high < low, key not found
18 }
19 }
The binary search returns the index of the search key if it is contained in the list (line 12).
Otherwise, it returns
-low - 1
(line 17).
What would happen if we replaced
(high >= low)
in line 7 with (
high > low
)? The
search would miss a possible matching element. Consider a list with just one element. The
search would miss the element.
Does the method still work if there are duplicate elements in the list? Yes, as long as the
elements are sorted in increasing order. The method returns the index of one of the matching
elements if the element is in the list.
To better understand this method, trace it with the following statements and identify
low
and
high
when the method returns.
int
[] list = {
2
,
4
,
7
,
10
,
11
,
45
,
50
,
59
,
60
,
66
,
69
,
70
,
79
};
int
i = BinarySearch.binarySearch(list,
2
);
// Returns 0
int
j = BinarySearch.binarySearch(list,
11
);
// Returns 4
int
k = BinarySearch.binarySearch(list,
12
);
// Returns -6
int
l = BinarySearch.binarySearch(list,
1
);
// Returns -1
int
m = BinarySearch.binarySearch(list,
3
);
// Returns -2
Here is the table that lists the
low
and
high
values when the method exits and the value
returned from invoking the method.
Method
Low
High
Value Returned
binarySearch(list, 2)
0
1
0
binarySearch(list, 11)
3
5
4
binarySearch(list, 12)
5
4
-6
binarySearch(list, 1)
0
-1
-1
binarySearch(list, 3)
1
0
-2
Note
Linear search is useful for finding an element in a small array or an unsorted array, but
it is inefficient for large arrays. Binary search is more efficient, but it requires that the
array be presorted.
binary search benefits
Search WWH ::
Custom Search