import java.util.*;

public class binsearch {

	public static void main(String[] args) {

		int[] arr = new int[20];
		Random r = new Random();
		for (int i=0; i<20; i++)
			arr[i] = r.nextInt(100);
		Arrays.sort(arr);
		for (int i=0; i<20; i++)
			System.out.print(arr[i]+" ");
		System.out.println();

		for (int i=0; i<100; i++)
			if (search(arr, i))
				System.out.println("found "+i);
	}

	public static boolean search(int[] arr, int searchval) {
		return searchRec(arr, 0, arr.length-1, searchval);
	}
	// Pre-condition: arr is in sorted order.
	// Post-condition: returns true iff searchval is in arr[low...high].
	public static boolean searchRec(int[] arr, int low, int high, int searchval) {

		// Empty search space.
		if (low > high) return false;

		int mid = (low+high)/2;

		// Value is in the left half.
		if (searchval < arr[mid])
			return searchRec(arr, low, mid-1, searchval);

		// Right half.
		else if (searchval > arr[mid])
			return searchRec(arr, mid+1, high, searchval);

		// Got it exactly.
		else
			return true;
	}
}