package binarySearch;
import java.util.Collections;
import java.util.Random;


public class Sorter {
	private static int CAPACITY = 1000;
	private static int depth = 0;
	/**
	 * @param args
	 */
	public static void main(String[] args) {

		int[] list = new int[CAPACITY]; // array that can hold CAPACITY integers
		fillArray(list); // fill the array with r
		int target = list[new Random().nextInt(CAPACITY)]; // generate a random number

		System.out.println("Searching for " + target );
		boolean isThere = contains(list, target); 
		System.out.println("\n"+isThere);
	}

	// Fills the array with sorted random numbers 
	private static void fillArray( int[] list ) {
		Random r = new Random(); // random number generator 

		for(int i=0; i<list.length; i++) { // fill the array with random integer values
			list[i] = r.nextInt(CAPACITY*10); // generate a random number from 0 to CAPACITY*10
		}
		
		bubbleSort(list);	// sort the array using our bad bubble-sort method below
	}

	// determines if the value is contained in the list via
	// brute-force search from the beginning to the end of the list.
	// Note: it does not matter if the list is sorted or not.
	private static boolean bruteForcecontains( int[] list, int target ) {
		boolean isThere = false; // 1

		for( int value : list ) { // 1 in best case, N/2 on average
			if( target == value ) {  
				isThere = true; 
				break; 
			}
		}

		return isThere;
	}

	// This method utilizes the "Splitting rule", or Binary Search,
	// to see if a target value is contained in the list. Note that this
	// algorithm works ONLY if the list is already sorted!
	private static boolean contains(int[] list, int target ) {
		depth = 0;
		int lo = 0; // initial lower bound of splitting interval
		int hi = list.length-1; // initial upper bound of splitting interval

		int index = binarySearch(list, target, lo, hi);
		if( index == -1 ) 
			return false;
		
		return true;
	}
	
	// recursively performs a binary search of an array between the specified
	// hi and lo intervals to see if the given target exists within the interval
	// Uses the "splitting rule".
	// If the target is found, returns the index where found.
	// If the target is not found, returns -1
	private static int binarySearch(int[] list, int target, int lo, int hi ) {
		System.out.println("Depth: " + depth + ", Low: "+ lo + ", High: " + hi );
		int index = -1;
		depth++;
		return -1;
	}

	// Sorts an array using the bubble-sort algorithm.
	// Note: Don't use this algorithm! It is BAD because of quadratic behavior.
	private static void bubbleSort( int[] list ) {
		int N = list.length; // 1

		for( int i=0; i<N; i++ ) { // 2N+2
			int min = list[i]; 	   // N

			for( int j=i; j<N; j++ ) { // N*N + 4N

				if( list[j] < min ) { // (N*N + N)/2
					int temp = min; // (N*N + N)/2
					min = list[j];// (N*N + N)/2
					list[j] = temp;// (N*N + N)/2
				}
			}
			list[i] = min; // N
		}
	}



}

/*
		if( hi-lo <= 1) { // search interval has been narrowed to 1 or 2 values!
			if( target == list[lo] )
				index = lo;
			else if( target == list[hi] )
				index =  hi;

			if( index == -1 ) 
				System.out.println(target + " not found between " + list[lo] + " and " + list[hi]);
			else 
				System.out.println("Found " + target + " at " + index);

			return index;
			
		} else { // interval contains at least three values
			int mid = (lo+hi)/2; // split the interval
			if( target < list[mid+1] ) // target must be in lower half (if at all)
				return binarySearch(list, target, lo, mid);
			else						// target must be in upper half (if at all)
				return binarySearch(list, target, mid+1, hi);
		}

*/