Java Reference
In-Depth Information
low
mid
high
key is 11
key
50
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9] [10] [11]
[12]
list
2
4
7
10
11
45
50
59
60
66
69
70
79
low
mid
high
[0]
[1]
[2]
[3]
[4]
[5]
key
7
list
2
4
7
10
11
45
low mid high
[3]
[4]
[5]
key
11
list
10
45
11
F
IGURE
6.10
Binary search eliminates half of the list from further consideration after each
comparison.
public static int
binarySearch(
int
[] list,
int
key) {
int
low =
0
;
int
high = list.length -
1
;
public static int
binarySearch(
int
[] list,
int
key) {
int
low =
0
;
int
high = list.length -
1
;
while
(high >= low) {
int
mid = (low + high) /
2
;
int
mid = (low + high) /
2
;
if
(key < list[mid])
high = mid -
1
;
else if
(key == list[mid])
return
mid;
els
low = mid +
1
;
if
(key < list[mid])
high = mid -
1
;
else if
(key == list[mid])
return
mid;
els
low = mid +
1
;
}
}
return
-
1
;
// Not found
}
(a) Version 1
(b) Version 2
F
IGURE
6.11
Binary search is implemented incrementally.
indicate that the key matches
list[0]
. A good choice is to let the method return
-low - 1
if the key is not in the list. Returning
-low - 1
indicates not only that the key is not in the list,
but also where the key would be inserted.
The complete program is given in Listing 6.7.
L
ISTING
6.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
8
9
if
(key < list[mid])
10 high = mid -
1
;
11
while
(high >= low) {
int
mid = (low + high) /
2
;
first half
else if
(key == list[mid])
