/*
   The binary search algorithm assumes that an array A is sorted, such as
     2 4 5 8 9 12 15 18

   The algorithm searches for an element by breaking the array in half each
   time.  It is a very efficient algorithm (O(log n) time).  

   We maintain two variables: start and end, which keeps track of the 
   current segment of the array we're examining.  Initially, start=0 and
   end=A.length-1, which indicates the entire array.
   
   The algorithm applies the following steps repeatedly:
   
   Calculate the middle index of the array mi = (start+end)/2

   Compare x with element at A[mi]:
  
     if (x==A[mi]) then we've found what we're looking for and can stop.

     if (x<A[mi]) then x must be on the left portion of the segment,
     so we narrow segment we're searching by setting end=mi-1;

     Similarly, if (x>A[mi]) then start=mi+1;
    
     Finally, if ever start>end, that means that x is not in the 
     array, and we can quit.
   
*/

public class bsearch
{
   
    // the following function determines if an array is sorted:
    public static boolean sorted(int[] A)
    {
	boolean answer = true;
	for(int i=0;i<A.length-1 && answer;i++)
	    {
		if (A[i]>A[i+1]) answer = false;
	    }
	return answer;
    } // sorted


    // binary search (using loop): returns position of element, -1 if not found

    public static int search(int x, int[] A)
    {
	int start=0;
	int end=A.length-1;
	int mi=0;
	boolean stop = false;
	while (!stop)
	    {
		mi = (start+end)/2;
                if (start>end) {stop=true; mi=-1;}
		else if (x==A[mi]) { stop = true; }
		else if (x<A[mi]) end=mi-1;
		else start=mi+1;
	    } // while
	return mi;
    }//search

    // version using recursion:
    public static int rsearch(int x, int[] A, int start, int end)
    {
	if (start>end) return -1; // not found;
	int mi= (start+end)/2;
	if (A[mi]==x) return mi;
	else if (x<A[mi]) return rsearch(x,A,start,mi-1);
	else return rsearch(x,A,mi+1,end);
    }


    // non-binary search (not assuming sorted list)
    public static int dsearch(int x, int[] A)
    {
	int a = -1;
	for(int i=0;i<A.length &&a==-1;i++)
	{ if (x==A[i]) a = i; }
	return a;
    }

    // generates a random, sorted array:
    public static int[] genarray(int size)
    {   int r; 
	int[] A = new int[size];
	A[0] = (int)(Math.random() * size);
	for(int i=1;i<size;i++)
	    {
		r = (int)(Math.random() *size) + A[i-1] + 1;
		A[i] = r;
	    }
	return A;
    }

    public static void main(String[] args)
    {
	long t1, t2, t3;  // record times
	int result;
	int n = Integer.parseInt(args[0]);
	int[] A = new int[n];
	for(int i=0;i<A.length;i++) A[i] = i*2;
	t1 = System.currentTimeMillis();
	result = search(15,A);
	t2 = System.currentTimeMillis() -t1;
	t1 = System.currentTimeMillis();
	result = dsearch(15,A);
	t3 = System.currentTimeMillis() -t1;
	System.out.println("time for binary search: "+t2+"ms");
	System.out.println("time for straight search: "+t3+"ms");
    }
   
} // besearch