// Arup Guha
// 7/10/2012
// Binary Search
// Written for BHCSI - Introduction to arrays and static methods.

import java.util.*;

public class binsearch2 {
	
	// Constants for our program.
	public final static int NUMVALS = 20;
	public final static int MAXVAL = 100000;
	public final static boolean PRINTFLAG = true;
	
	public static void main(String[] args) {
		
		Scanner stdin = new Scanner(System.in);
		
		// Create array.
		int[] myarray = makeArray(NUMVALS, MAXVAL);
		if (PRINTFLAG) printArray(myarray);
		
		// Check if the array is already sorted or not.
		if (!isSorted(myarray))
			System.out.println("not sorted.");
			
		// Now sort.
		Arrays.sort(myarray);
		if (PRINTFLAG) printArray(myarray);
		
		// Now it should be sorted.
		if (isSorted(myarray))
			System.out.println("is sorted.");
		
		// Get the value to search for.
		System.out.println("For which value do you want to search?");
		int val = stdin.nextInt();
		
		// Search for it and print out the results.
		if (binsearch2.search(myarray, val))
			System.out.println(val+" is in the array.");
		else
			System.out.println(val+" is NOT in the array.");
			
	}
	
	// Returns true iff array is in sorted order.
	public static boolean isSorted(int[] array) {
		
		// Look to see if any adjacent pairs are out of order.
		for (int i=0; i<array.length-1; i++)
			if (array[i+1] < array[i])
				return false;
				
		// If not, it's sorted.
		return true;
	}
	
	// Runs a binary search for value in array. Assumes array is sorted from
	// smallest to largest.
	public static boolean search(int[] array, int value) {
		
		// Set bounds for binary search.
		int low = 0;
		int high = array.length - 1;
		
		// Search until there's no search space.
		while (low <= high) {
			
			// Look in the middle.
			int mid = (low+high)/2;
			
			// Reduce the search space as necessary.
			if (value > array[mid])
				low = mid+1;
			else if (value < array[mid])
				high = mid-1;
			else
				return true;
			
		}
		
		// If we get here, the value isn't in the array.
		return false;
	}
	
	// Returns an array with size elements in the range [1,max].
	public static int[] makeArray(int size, int max) {
		
		Random r = new Random();
		
		int[] array = new int[size];
		
		for (int i=0; i<array.length; i++)
			array[i] = r.nextInt(max) + 1;
			
		return array;
	}
	
	// Prints the contents of array.
	public static void printArray(int[] array) {
		
		for (int i=0; i<array.length; i++)
			System.out.print(array[i]+" ");
		System.out.println();
	}
}