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