/*
 * Copyright Dr. Marek A. Suchenek 2012, 2013, 2014
 * 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 AverageRT
//This is a copy of class bSearch devoid of all comments except for the copyright not and this comment
{

    public static void main(String[] args)
    {
           int[] Array;
           int N, noFit = 0;
           Boolean match = true, approx = true;
 for (N = 2; N<=200; N++)
 {
        Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = 2*i+1;
        }
        System.out.println("*** " + N + "-element sorted array to be searched ***");
        System.out.println("Successful searches in Array");
        Bcnt.clr();
        for (int i = 0; i < N; i++)
        {
            binSearch(Array, 0, N-1, 2*i+1);
        }
        System.out.println(">>> If values in the 2 following lines are exactly exactly equal then the theoretic result coincides with the running of the actual program.");
        System.out.print(">>> Performed comps(" + N +")");
        Bcnt.outln(" = ");
        System.out.println(">>> Theoretic accumulative number of comps in successful searches in an " + N
                + "-element array = " + (((N+1)*(int)(Math.ceil(Math.log(N+1)/Math.log(2))))-2*maxpower2(N)+1));
        if (Bcnt.get() == (((N+1)*(int)(Math.ceil(Math.log(N+1)/Math.log(2))))-2*maxpower2(N)+1))
            System.out.println("Match!");
        else
        {
            System.out.println("No match!");
            match = false;
        }
        double avg_succ = 1.0*Bcnt.get()/N;
        System.out.println("Avg = " + avg_succ);
        System.out.println("Approximate low value of avg = " + (Math.log(N+1)/Math.log(2)-1));
        System.out.println("Approximate high value of avg = " + (Math.log(N+1)/Math.log(2)-.9));
        if (((Math.log(N+1)/Math.log(2)-1) <= avg_succ) && (avg_succ <= (Math.log(N+1)/Math.log(2)-.9)))
            System.out.println("Fits in!");
        else
        {
            System.out.println("Does NOT fit in!");
            approx = false;
            noFit = N;
        }
        System.out.println("Unuccessful searches in Array");

        Bcnt.clr();
        for (int j = 0; j < N+1; j++)
        {
            binSearch(Array, 0, N-1, 2*j);
        }
        System.out.println(">>> If values in the 2 following lines are exactly exactly equal then the theoretic result coincides with the running of the actual program.");
        System.out.print(">>> Performed comps(" + N +")");
        Bcnt.outln(" = ");
        System.out.println(">>> Theoretic accumulative number of comps in unsuccessful searches in an " + N
                + "-element array = " + (((N+1)*(int)(Math.ceil(Math.log(N+1)/Math.log(2))))-2*maxpower2(N)+N+1));
        if (Bcnt.get() == (((N+1)*(int)(Math.ceil(Math.log(N+1)/Math.log(2))))-2*maxpower2(N)+N+1))
            System.out.println("Match!");
        else
        {
            System.out.println("No match!");
            match = false;
        }
        double avg_fail = 1.0*Bcnt.get()/(N+1);
        System.out.println("Avg = " + avg_fail);
        System.out.println("Approximate low value of avg = " + (Math.log(N+1)/Math.log(2)));
        System.out.println("Approximate high value of avg = " + (Math.log(N+1)/Math.log(2)+.1));
        if (((Math.log(N+1)/Math.log(2)) <= avg_fail) && (avg_fail <= (Math.log(N+1)/Math.log(2)+.1)))
            System.out.println("Fits in!");
        else
        {
            System.out.println("Does NOT fit in!");
            approx = false;
            noFit = N;
        }
        System.out.println("Difference between the unsuccessful and successful = " + (avg_fail - avg_succ));
        System.out.println();
 }
   if (match) System.out.println("All experiments matched theoretic values");
   else System.out.println("Some experiments did NOT match theoretic values");
   if (approx) System.out.println("All experiments did fit between approximations");
   else
   {
       System.out.println("Some experiments did NOT fit between approximations");
       System.out.println("Latest that did NOT was for N = " + noFit);
   }
}
    public static int binSearch (int[] Elements, int first, int last, int Key)
    {
        if (first > last) return -1;
        int mid = (first + last)/2;
        int comp = compare(Key, Elements[mid]);
        Bcnt.incr();
        if (comp < 0) return binSearch(Elements, first, mid-1, Key);
        if (comp > 0) return binSearch(Elements, mid+1, last, Key);
        return mid;
    }

    private static int compare (int m, int n)
    {
        if (m < n) return -1;
        if (m > n) return 1;
        return 0;
    }
    
    private static int maxpower2(int n)
//            Computes the max power of 2 not greater than n (= 2^floor(log_2 n))
    {
        int power2 = 1;
        while (2*power2 <= n)
        {
            power2 *=2;
        }
        return power2;
    }


}