package org.tbray.ongoing;

import java.io.*;
import java.util.*;

public class BinarySearch
{
    static public int search1(int [] array, int target)
    {
	int high = array.length, low = -1, probe;
	while (high - low > 1)
	{
	    probe = (high + low) >>> 1;
	    if (array[probe] > target)
		high = probe;
	    else
		low = probe;
	}
	if (low == -1 || array[low] != target)
	    return -1;
	else
	    return low;
    }

    static public int search(int [] array, int target)
    {
	int high = array.length, low = -1, probe;
	while (high - low > 1)
	{
	    probe = (high + low) >>> 1;
	    if (array[probe] < target)
		low = probe;
	    else
		high = probe;
	}
	if (high == array.length || array[high] != target)
	    return -1;
	else
	    return high;
    }

    static public int [] range(int [] array, int floor, int ceiling)
    {
	int [] answer = new int[2];
	int high, low, probe;

	// work on floor
	high = array.length; low = -1;
	while (high - low > 1)
	{
	    probe = (high + low) >>> 1;
	    if (array[probe] < floor)
		low = probe;
	    else
		high = probe;
	}
	answer[0] = low;

	// work on ceiling
	high = array.length; low = -1;
	while (high - low > 1)
	{
	    probe = (high + low) >>> 1;
	    if (array[probe] > ceiling)
		high = probe;
	    else
		low = probe;
	}
	answer[1] = high;
	return answer;
    }
	
    public static void main( String args[] )
    {
	int [] test = { 2, 4, 4, 6, 8 };

	// sanity-check "search"
	BinarySearch searcher = new BinarySearch();
	for (int i = 0; i < 10; i++)
	    System.out.println("Search1 for " + i + " => " +
			       search1(test, i) + " search => " +
			       search(test, i));

	// sanity-check "range"
	int floor, ceiling;
	for (ceiling = 0; ceiling < 10; ceiling++)
	    for (floor = 0; floor <= ceiling; floor++)
	    {
		int [] answer = range(test, floor, ceiling);
		System.out.print("Range [" + floor + "," + ceiling +
				 "] = [");
		if (answer == null)
		    System.out.println("*,*]");
		else
		    System.out.println(answer[0] + "," + answer[1] + "]");
	    }

	// now let's do some time trials
	Random r = new Random(666);

	// default is a million, but can override on command line
	int howBig = 1000000;
	if (args.length > 0)
	    howBig = Integer.parseInt(args[0]);

	System.out.println("How big? " + howBig);
	
	// load up array to be searched
	int [] a1 = new int[howBig];
	int [] a5 = new int[howBig * 5];
	int [] a10 = new int[howBig * 10];
	int val1, val2, val3;
	val1 = val2 = val3 = 10;
	for (int i = 0; i < howBig * 10; i++)
	{
	    if (i < howBig)
		a1[i] = a5[i] = a10[i] = val1 = val3;
	    else if (i < howBig * 5)
		a5[i] = a10[i] = val2 = val3;
	    else a10[i] = val3;
	    val3 += 1 + r.nextInt(10);
	}

	// preload 3 arrays of random search targets to get that
	//  out of the timing loop
	int [] target1 = new int[10000];
	int [] target2 = new int[10000];
	int [] target3 = new int[10000];

	for (int i = 0; i < 10000; i++)
	{
	    target1[i] = r.nextInt(val1);
	    target2[i] = r.nextInt(val2);
	    target3[i] = r.nextInt(val3);
	}

	for (int i = 0; i < 10; i++)
	{
	    searchALot(a1, target1);
	    searchALot(a5, target2);
	    searchALot(a10, target3);
	    System.out.println("=========================");
	}
    }

    static private int searchALot(int [] array, int [] targets)
    {
	long before = System.currentTimeMillis();
	int found = 0;
	for (int i = 0; i < targets.length; i++)
	{
	    if (search(array, targets[i]) != -1)
		found++;
	}
	long after = System.currentTimeMillis();

	double seconds = ((double) (after - before)) / 1000.0;
	System.out.println(seconds + ", size " + array.length);

	return found;
    }
}