public class ArraySearcher
1: //ArraySearcher.java
2:
3: /**
4: * Class for searching an already sorted array of integers.
5: */
6: public class ArraySearcher
7: {
8: private int[] a;
9:
10: /**
11: Precondition: theArray is full and is sorted
12: from lowest to highest.
13: */
14: public ArraySearcher
15: (
16: int[] theArray //in
17: )
18: {
19: a = theArray; //a is now another name for theArray.
20: }
21:
22: /**
23: If target is in the array, returns the index of an occurrence
24: of target. Returns -1 if target is not in the array.
25: */
26: public int find
27: (
28: int target //in
29: )
30: {
31: return binarySearch(target, 0, a.length - 1);
32: }
33:
34: //Uses binary search to search for target in a[first] through
35: //a[last] inclusive. Returns the index of target if target
36: //is found. Returns -1 if target is not found.
37: private int binarySearch
38: (
39: int target, //in
40: int first, //in
41: int last //in
42: )
43: {
44: int result;
45: if (first > last)
46: result = -1;
47: else
48: {
49: int mid = (first + last) / 2;
50: if (target == a[mid])
51: result = mid;
52: else if (target < a[mid])
53: result = binarySearch(target, first, mid - 1);
54: else //(target > a[mid])
55: result = binarySearch(target, mid + 1, last);
56: }
57: return result;
58: }
59: }