RecursiveSearch.java

/*
    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<arr.length; i++) {
            x += (int)(Math.random() * 3 + 1);
            arr[i] = x;
        }

// Time how long it takes to find the numbers 1 to 200000
        // using the first linear search.
        hits = 0;
        misses = 0;
        startTime = System.currentTimeMillis();
        System.out.print("First linear search:  ");
        for (int i=1; i<=TRIES; i++) {
            if (i % 1000 == 0) System.out.print("\b" + spin[spinNdx = ++spinNdx % 4]);
            if (rlinearSearch1(arr, i, 0) == -1) misses++;
            else hits++;
        }
        elapsedTime = System.currentTimeMillis() - startTime;
        System.out.println("\b \nHits: " + hits + "   Misses: " + misses
            + "    Elapsed time: " + df.format(elapsedTime) + "ms");

// Time how long it takes to find the numbers 1 to 200000
        // using the second linear search.
        hits = 0;
        misses = 0;
        startTime = System.currentTimeMillis();
        System.out.print("\nSecond linear search:  ");
        for (int i=1; i<=TRIES; i++) {
            if (i % 1000 == 0) System.out.print("\b" + spin[spinNdx = ++spinNdx % 4]);
            if (rlinearSearch2(arr, i, 0) == -1) misses++;
            else hits++;
        }
        elapsedTime = System.currentTimeMillis() - startTime;
        System.out.println("\b \nHits: " + hits + "   Misses: " + misses
            + "    Elapsed time: " + df.format(elapsedTime) + "ms");

// Time how long it takes to find the numbers 1 to 200000
        // using the binary search.
        hits = 0;
        misses = 0;
        startTime = System.currentTimeMillis();
        System.out.print("\nBinary search:  ");
        for (int i=1; i<=TRIES; i++) {
            if (i % 1000 == 0) System.out.print("\b" + spin[spinNdx = ++spinNdx % 4]);
            if (rbinarySearch(arr, i, 0, arr.length-1) == -1) misses++;
            else hits++;
        }
        elapsedTime = System.currentTimeMillis() - startTime;
        System.out.println("\b \nHits: " + hits + "   Misses: " + misses
            + "    Elapsed time: " + df.format(elapsedTime) + "ms");
    }

// rlinearSearch1 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 does not have to be
    // sorted. The entire array is searched if needed.
    public static int rlinearSearch1(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 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);
    }
}