Java Reference
In-Depth Information
6 /**
7
Constructs a BinarySearcher.
8 @param anArray
a sorted array of integers
9 */
10
public
BinarySearcher(
int
[] anArray)
11 {
12 a = anArray;
13 }
14
15 /**
16
Finds a value in a sorted array, using the binary
17
search algorithm.
18 @param v
the value to search
19 @return
the index at which the value occurs, or -1
20
if it does not occur in the array
21 */
22
public int
search(
int
v)
23 {
24
int
low =
0
;
25
int
high = a.length -
1
;
26
while
(low <= high)
27 {
28
int
mid = (low + high) /
2
;
29
int
diff = a [mid] - v;
30
31
if
(diff ==
0
) // a[mid] == v
32
return
mid;
33
else if
(diff <
0
) // a[mid] <
v
34 low = mid +
1
;
35
else
36 high = mid -
1
;
37 }
38
return
-1
;
39 }
40
41
private int
[] a;
42 }
652
653
Let us determine the number of visits of array elements required to carry out a search.
We can use the same technique as in the analysis of merge sort. Because we look at
