/** Binary.java - Binary search using three methods. The first is more 
	intuitive, but it is supposed to be slower. Yet in my runs it is 
	the fastest
*/


public class Binary
{

    /** Given a sorted array, we search for who using binary search.
	We return a position where found, or -1 if not there
    */
    public static int binary1(int[] a, int who) {
	int left = 0; 
	int right = a.length-1;
	while (left <= right) {
	    // Up to now who has not been found
	    // Thus if in a it will be between left and right
	    int mid = left + (right - left) /2; // To avoid overflow
	    if (who < a[mid])
		right = mid - 1;
	    else if (who > a[mid])
		left = mid + 1;
	    else
		return mid;
	}
	return -1;
    }

    /** Given a sorted array, we search for who using binary search.
	We return a position where found, or -1 if not there
    */
    public static int binary2(int[] a, int who) {
	int m = a.length;
	int p = (m-1) / 2;
	while (m > 0) {
	    if (who < a[p]) {
		m = (m-1)/2;
	        p = p - m/2 - 1; 
	    } else if (who > a[p]) {
		m = m/2;
		p = p + (m-1)/2 + 1;
	    } else 
		return p;
	}	
	return -1;
    }

    /** Given a sorted array, we search for who using binary search.
	We return a position where found, or -1 if not there
    */
    public static int binary3(int[] a, int who) {
	int m = a.length;
	int p = (m-1) / 2;
	while (m > 0) {
	    m = m/2;
	    if (who <= a[p]) {
	        p = p - (m+1)/2; 
	    } else {
		p = p + (m-1)/2 + 1;
	    } 
	}
	if (p < a.length && who == a[p])
	    return p;
	else
	    return -1;
    }


    public static void main(String[] args) throws Exception {
	final int TRIES = 1000000;
	int[] a = {1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33};
	int n = a.length;
	int where;
	long before;
	long after;
	before = System.currentTimeMillis();
	for (int j = 0; j < TRIES; j++)
	    for (int k = 0; k < 2*n+1; k++) {
		where = binary1(a, k);
//		System.out.printf("who = %d, \tvalue = %d\n", k, where); 
	    }
	after = System.currentTimeMillis();
	System.out.printf("before=%d, after=%d\n", before, after);
	System.out.printf("The difference is %d\n", after - before);
	System.out.print("---------------------------------------------\n");
	before = System.currentTimeMillis();
	for (int j = 0; j < TRIES; j++)
	    for (int k = 0; k < 2*n+1; k++) {
		where = binary2(a, k);
//		System.out.printf("who = %d, \tvalue = %d\n", k, where); 
	    }
	after = System.currentTimeMillis();
	System.out.printf("before=%d, after=%d\n", before, after);
	System.out.printf("The difference is %d\n", after - before);
	System.out.print("---------------------------------------------\n");
	before = System.currentTimeMillis();
	for (int j = 0; j < TRIES; j++)
	    for (int k = 0; k < 2*n+1; k++) {
		where = binary3(a, k);
//		System.out.printf("who = %d, \tvalue = %d\n", k, where); 
	    }
	after = System.currentTimeMillis();
	System.out.printf("before=%d, after=%d\n", before, after);
	System.out.printf("The difference is %d\n", after - before);
	System.out.print("---------------------------------------------\n");
    }
}