public class OrSearch {
    public static void main(String[] args) {
	if (args.length==0)
	    {
		System.out.println("java OrSearch sizeOfSearchSpace numberOfTrials");
		return;
	    }
	int reps = Integer.parseInt(args[1]);
	int steps=0;
	int[] arr = new int[Integer.parseInt(args[0])];
	arr[0]=(int)(Math.random()*10);
	for (int ii=1; ii<arr.length; ii++)
	    arr[ii] = arr[ii-1]+1+(int)(Math.random()*20);
	for (int kk=0; kk<reps; kk++) {
		int tgt = arr[(int)(Math.random()*arr.length)];
		int hi=arr.length-1;
		int lo=0;
		int mid=hi/2;
		steps++;
		while (arr[mid] !=tgt)
		    {
			steps++;
			if (arr[mid]>tgt) hi=mid-1;
			if (arr[mid]<tgt) lo=mid+1;
			mid=(lo+hi)/2;
		    }
	    }
	System.out.println("reps="+reps+"   steps="+steps+"    average="+(steps/reps));
    }
}