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