import java.util.*;
class BinarySearch{

	int record[];
	int recordLength = 300;

	public BinarySearch(){

		Random r = new Random(2019);
		record = new int[recordLength];

		for(int i = 0; i < record.length; i++){
			record[i] = r.nextInt(3000);
		}//for

		Arrays.sort(record);

		System.out.println(Arrays.toString(record));

		int toFind = 1336;

		binarySearch(toFind, 0, record.length-1); // recursive

		binarySearch2(toFind, 0, record.length-1); // iterable


	}//constructor

	public static void main(String args[]){

		new BinarySearch();

	}//main


	/*
	 * Method binarySearch() is the method that you need to complete, you are only allowed to use RECURSIVE method to fulfill it
	 *
	 * Print out "Not found." if the target is not contained in record so that you need to insert the following line:
	 *
	 * System.out.println("Not found.");
	 *
	 * Print out "Found" if the record do contain target
	 * In addition, you still have to print out the index of the target when you found it so that you need to insert the following line:
	 *
	 * System.out.println("Found at: " + theIndexOfWhereTargetIs);
	 *
	 */

	public void binarySearch(int target, int low, int high){

		int mid = (low+high)/2;

		if(low > high){
			System.out.println("Not found.");
		}else{
			if(record[mid]==target){
				System.out.println("Found at: " + mid);
			}else if(record[mid]>target){
				binarySearch(target, low, mid-1);
			}else{
				binarySearch(target, mid+1, high);
			}//else

		}//else

	}//binarySearch


	/*
	 * not recursive way (iterable)
	 */
	public void binarySearch2(int target, int low, int high){

		int mid;
		boolean found=false;
		while(low < high){

			mid = (low+high)/2;
			if(record[mid]==target){
				System.out.println("Found at: " + mid);
				found = true;
				break;
			}else if(record[mid]>target){
				high = mid-1;
			}else{
				low = mid + 1;
			}//else

		}//else

		if(!found)
			System.out.println("Not found.");

	}//binarySearch2

}//II_quiz_12_2019_solution