/*
 * Copyright Dr. Marek A. Suchenek 2012
 * Students currently enrolled in CSC 401 or CSC 501 class at CSUDH
 * can download and execute this program for their presonal educational use
 * provided they include this entire comment in their all copies.
 * All other use requires permission of the copyright holder.
 */

package binarysearch;

/**
 *
 * @author Dr. Marek A. Suchenek
 */
public class bSearch {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args)
    //Driver for binSearch
    {
           int[] Array; //array to be searched
           int N; //number of elements - will vary in order to test the running time
 for (N = 1; N<=1000; N++) //this loop makes binSearch run on N-element arrays for all Ns in the range
 {
        Array = new int[N];
        //filling Array with increasing positive odd numbers
        for (int i = 0; i < N; i++)
        {
            Array[i] = 2*i+1;// this will make search for any even number unsuccessful
        }
        System.out.println("*** " + N + "-element sorted array to be searched ***");
//        for (int i = 0; i < N; i++) System.out.print(Array[i] + " ");
//        System.out.println();

        Bcnt.clr(); //will count comparisons while searching Array
        System.out.println("Searching Array[" + N + "] for 0");
        //Search for 0 in Array begins:
        //it will return -1 if not found or the index of 2*N in Array if found
        int found = binSearch(Array, 0, N-1, 0);
        if (found == -1) System.out.print("Unsuccessful search: " + "0 is not in Array");
        else System.out.print("Successful search: " + "0 is in Array at index " + found);
        System.out.println();
        System.out.print("comps(" + N +")");
        Bcnt.outln(" = ");
        System.out.println("Theoretic worst-case number of comps in an " + N
                + "-element array = " + (int)Math.ceil(Math.log(N+1)/Math.log(2)));
        System.out.println();

        Bcnt.clr(); //will count comparisons while searching Array
        System.out.println("Searching Array[" + N + "] for " + (2*N-1) );
        //Search for 2*N in Array begins:
        //it will return -1 if not found or the index of 2*N-1 in Array if found
        found = binSearch(Array, 0, N-1, 2*N-1);
        if (found == -1) System.out.print("Unsuccessful search: " + (2*N-1) + " is not in Array");
        else System.out.print("Successful search: " + (2*N-1) + " is in Array at index " + found);
        System.out.println();
        System.out.print("comps(" + N +")");
        Bcnt.outln(" = ");
        System.out.println("Theoretic worst-case number of comps in an " + N
                + "-element array = " + (int)Math.ceil(Math.log(N+1)/Math.log(2)));
        System.out.println();

        Bcnt.clr(); //will count comparisons while searching Array
        System.out.println("Searching Array[" + N + "] for " + 2*N );
        //Search for 2*N in Array begins:
        //it will return -1 if not found or the index of 2*N in Array if found
        found = binSearch(Array, 0, N-1, 2*N);
        if (found == -1) System.out.print("Unsuccessful search: " + 2*N + " is not in Array");
        else System.out.print("Successful search: " + 2*N + " is in Array at index " + found);
        System.out.println();
        System.out.print("comps(" + N +")");
        Bcnt.outln(" = ");
        System.out.println("Theoretic worst-case number of comps in an " + N
                + "-element array = " + (int)Math.ceil(Math.log(N+1)/Math.log(2)));
        System.out.println();
 }
}
    public static int binSearch (int[] Elements, int first, int last, int Key)
    //binSearch will return -1 if Key not found in Elements or the index of Key in Elements if found
    {
        if (first > last) return -1; //the range of Elements is empty so Key is not in there
        int mid = (first + last)/2; //compute the midpoint as ceiling of the average of first and last
        int comp = compare(Key, Elements[mid]); //returns -1 if Key < Elements[mid], 0 if Key == Elements[mid], 1 if Key > Elements[mid]
        Bcnt.incr(); //increments counter of comparisons done
        if (comp < 0) return binSearch(Elements, first, mid-1, Key); //search in the left half
        if (comp > 0) return binSearch(Elements, mid+1, last, Key); //search in the right half
        return mid; //comp = 0 so Key == Elements[mid] and mid is the index of Key in Elements
    }

    private static int compare (int m, int n)
    //this method could be rewritten to compare anything, like Strings, lists, sets, etc.
    //it returns -1 if m < n, 0 if m == n, 1 if m > n
    {
        if (m < n) return -1;
        if (m > n) return 1;
        return 0;
    }


}