import java.util.*;


public class binarysearch {

	public static void main(String[] args) {
	int[] list = new int[100000];
	int[] check = new int[100000];
	int i;
	
	
	for(i=0; i<100000; i++){
		list[i]=i;  //array of searchable values
		check[i]=(int)(Math.random()*100000);   //holds values that are being looked for
	}
	
	/*
	for(i=0; i<10; i++){
		System.out.println("Iterative search: "+check[i]+" was found at "+iterative(list,check[i]));
		System.out.println("Recursive search: "+check[i]+" was found at "+recursive(list,check[i],list.length,0));
	}
	*/
	
	long time1, time2;
	Calendar before = Calendar.getInstance();	//before holds date and time before search
	time1 = before.getTimeInMillis();			//time1 holds the time before search in milliseconds
	
	System.out.println("Current time in milliseconds before iterative search is: "+time1);
	
	for(i=0; i<100000; i++)
		iterative(list,check[i]);
	
	Calendar after = Calendar.getInstance();	//after holds date and time after search
	time2 = after.getTimeInMillis();			//time2 holds the time after search in milliseconds
	System.out.println("Current time in milliseconds after iterative search is: "+time2);
	System.out.println("Total time for iterative search is: "+(time2-time1));
	System.out.println("");
	
	before = Calendar.getInstance();
	System.out.println("Current time in milliseconds before recursive search is: "+time1);
	
	for(i=0; i<100000; i++)
		recursive(list,check[i],list.length,0);
	
	after = Calendar.getInstance();
	time2 = after.getTimeInMillis();
	System.out.println("Current time in milliseconds after recursive search is: "+time2);
	System.out.println("Total time for recursive search is: "+(time2-time1));
}
	
	public static int iterative(int[] x, int target) {
		int h = x.length; 				//h will be upper bound
		int l = 0, p;         			//l will be lower bound
		while(h > l){   				
			p = (h+l)/2;    			//p will be what is compared to target
			if(x[p]==target)
				return p;
			if(x[p]>target)
				h = p;      			//if target is greater, make lower bound = p
			else 
				l = p;      			//if target is less, make upper bound = p
		}
		return -1;
	}
	public static int recursive(int[] x, int target, int h, int l) {
		if(l > h)
			return -1;
		int p = (l+h)/2;
		if(target > x[p])
			return recursive(x, target, h, p+1);
		else if(target < x[p])
			return recursive(x, target, p-1, l);
		else
			return p;
	}
}