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