Code /* RecursiveSearch.java CIS 260 2/01/06 Demonstration of recursive linear and binary searching. This program may crash due to running out of available memory because of all the levels of recursion it is attempting. If you want to see it crash fast, then just increase the size of the arr array. */ import java.text.*; public class RecursiveSearch { static final int SIZE = 5000; static final int TRIES = 10000; public static void main(String[] args) { long startTime, elapsedTime; int hits, misses; char[] spin = { '|', '/', '-', '\\' }; int spinNdx = 0; DecimalFormat df = new DecimalFormat("0.00"); int[] arr = new int[SIZE]; // create an array of somewhat random integers // that is in sequential order int x = 0; for (int i=0; i= a.length) return -1; // not found if (a[start] == key) return start; // found, so return position else return rlinearSearch1(a, key, start+1); // keep searching } // rlinearSearch2 will search through an int array // for any key. It returns -1 if the key is not found. // If the key is found, it returns the position in the // array it was found at. The array must be sorted in // ascending order. This method will only search // through as much of the array as needed. public static int rlinearSearch2(int[] a, int key, int start) { if (start >= a.length) return -1; // not found if (a[start] == key) return start; // found, so return position else if (a[start] > key) return -1; // not found else return rlinearSearch2(a, key, start+1); // keep searching } // rbinarySearch will search through an int array // for any key. It returns -1 if the key is not found. // If the key is found, it returns the position in the // array it was found at. The array must be sorted in // ascending order. public static int rbinarySearch(int[] a, int key, int start, int end) { if (end < start) return -1; int middle = (end+start) / 2; if (a[middle] == key) return middle; else if (a[middle] > key) return rbinarySearch(a, key, start, middle-1); else return rbinarySearch(a, key, middle+1, end); } }