/*
    Search.java
    CIS 160
    11/08/04

    Demonstration of linear and binary searching.
*/

import java.text.*;

public class Search {
    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[100000];

        // 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<=200000; i++) {
            if (i % 1000 == 0) System.out.print("\b" + spin[spinNdx = ++spinNdx % 4]);
            if (linearSearch1(arr, i) == -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<=200000; i++) {
            if (i % 1000 == 0) System.out.print("\b" + spin[spinNdx = ++spinNdx % 4]);
            if (linearSearch2(arr, i) == -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<=200000; i++) {
            if (i % 1000 == 0) System.out.print("\b" + spin[spinNdx = ++spinNdx % 4]);
            if (binarySearch(arr, i) == -1) misses++;
            else hits++;
        }
        elapsedTime = System.currentTimeMillis() - startTime;
        System.out.println("\b \nHits: " + hits + "   Misses: " + misses
            + "    Elapsed time: " + df.format(elapsedTime) + "ms");
    }

    // linearSearch1 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 linearSearch1(int[] a, int key) {
        for (int i=0; i<a.length; i++) {
            if (a[i] == key) return i;
        }
        return -1;
    }

    // linearSearch2 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 linearSearch2(int[] a, int key) {
        for (int i=0; i<a.length; i++) {
            if (a[i] == key) return i;
            if (a[i] > key) return -1;
        }
        return -1;
    }

    // binarySearch 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 binarySearch(int[] a, int key) {
        int hi = a.length - 1;
        int lo = 0;
        int middle;
        while (hi >= lo) {
            middle = (hi + lo) / 2;
            if (a[middle] == key) return middle;
            else if (a[middle] > key) hi = middle - 1;
            else lo = middle + 1;
        }
        return -1;
    }
}