package analysis;

import java.util.Arrays;

public class BinarySearch {

    public static final int NOT_FOUND = -1;
    public static final int MAX_NUM = 1000000;
    public static void main(String[] args) {

        Integer testNums[] = {1,2,3,4,6,7,8,9,11,12,16,24,34,45};
        int numToFind = 12;
        
        System.out.println("\nSearching for "+numToFind+" in nums array...");
        System.out.println(recursiveBinarySearch(testNums, numToFind));
        
        Integer nums[] = new Integer[MAX_NUM];
        for (int i = 0; i < MAX_NUM; i++) {
            nums[i] = (int)(Math.random()*MAX_NUM);
        }        
        Arrays.sort(nums);               
//        for(Integer i: nums) System.out.print(i+" ");
//        System.out.println();

        long startTime, estimatedTime;
        numToFind = (int)(Math.random()*MAX_NUM);
        System.out.println("\nSearching for "+numToFind+" in nums array...");
        
        startTime = System.nanoTime();
        System.out.print("\nrecursiveBinarySearch: "
                + recursiveBinarySearch(nums, numToFind));
        estimatedTime = System.nanoTime() - startTime;
        System.out.println("\t (time: " + estimatedTime + " nanoseconds)");

        startTime = System.nanoTime();
        System.out.print("iterativeBinarySearch: "
                + iterativeBinarySearch(nums, numToFind));
        estimatedTime = System.nanoTime() - startTime;
        System.out.println("\t (time: " + estimatedTime + " nanoseconds)");
    }

    public static <AnyType extends Comparable<? super AnyType>> int recursiveBinarySearch(
            AnyType[] a, AnyType key) {
        return recursiveBinarySearch(a, key, 0, a.length - 1);
    }

    private static <AnyType extends Comparable<? super AnyType>> int recursiveBinarySearch(
            AnyType[] a, AnyType x, int low, int high) {
        System.out.println("low: "+low+" high: "+high);
        if (low > high)
            return NOT_FOUND;
        int mid = (low + high) / 2;
        if (a[mid].compareTo(x) < 0)
            return recursiveBinarySearch(a, x, mid + 1, high);
        else if (a[mid].compareTo(x) > 0)
            return recursiveBinarySearch(a, x, low, mid - 1);
        else
            return mid;
    }
    
    public static <AnyType extends Comparable<? super AnyType>>int iterativeBinarySearch(AnyType[] a, AnyType key) {
        int low = 0;
        int high = a.length - 1;

        while (low <= high) {
            int mid = (low + high) >> 1;
            int cmp = a[mid].compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }
        return NOT_FOUND; // key not found.
    }

}