import java.util.*;

/**
 * A few different static methods to find the index of a particular value in and
 * Integer ArrayList
 * 
 * @author dave
 * @date February 2, 2010
 */
public class BinarySearchExamples {
	/* NOTE ABOUT COMMENTS: Because these are examples where I may ask you to 
	 * "what does x do?" I have not included comments, however, you always should
	 * in your code :) 
	 */
	
	public static int search1(ArrayList<Integer> nums, int findMe){
		for( int i = 0; i < nums.size(); i++ ){
			if( nums.get(i).equals(findMe) ){
				return i;
			}
		}

		return -1;
	}
	
	public static int search1a(ArrayList<Integer> nums, int findMe){
		int returnMe = -1;
		
		for( int i = 0; i < nums.size(); i++ ){
			if( nums.get(i).equals(findMe) ){
				returnMe = i;
			}
		}

		return returnMe;
	}

	public static int search2(ArrayList<Integer> nums, int findMe){
		return search2Helper(nums, findMe, 0);
	}

	private static int search2Helper(ArrayList<Integer> nums, int findMe, int begin){
		if( begin >= nums.size() ){
			return -1;
		}else if( nums.get(begin).equals(findMe)){
			return begin;
		}else{
			return search2Helper(nums, findMe, begin+1);
		}
	}
	
	/**
	 * 
	 * 
	 * @pre nums is in ascending sorted order
	 * @param nums an ArrayList containing the sorted numbers
	 * @param findMe the element we're looking for
	 * @return Returns the index of the occurrence of findMe in nums if it occurs, -1 otherwise
	 */
	public static int binarySearch(ArrayList<Integer> nums, int findMe){ 
		int low = 0; 
		int high = nums.size() - 1; 

		while( low <= high ){ 
			int middle = (int)Math.floor((high+low)/2); 

			Integer middleElement = nums.get(middle);
			
			if( middleElement.equals(findMe) ){ 
				// weÕve found the element, so return it 
				return middle;	
			}else if( findMe < middleElement ){ 
				high = middle - 1; 
			}else{ 
				// findMe > middleElement 
				low = middle+1; 
			} 
		}
		
		return -1; 
	}
	
	/**
	 * @pre: nums is sorted in ascending order
	 */
	public int binarySearchRecursive(ArrayList<Integer> sorted, int findMe){ 
		return BinarySearchHelper(sorted, findMe, 0, sorted.size()-1); 
	} 
	
	private int BinarySearchHelper(ArrayList<Integer> sorted, int findMe, 
			int low, int high){ 
		if( low > high ){ 
			return -1; 
		}else{ 
			// find the mid-point of the list 
			int middle = (int)Math.floor((high+low)/2); 
			
			Integer middleElement = sorted.get(middle);
			
			if( middleElement.equals(findMe) ){
				// weÕve found the element, so return the index 
				return middle; 
			}else if( findMe < middleElement ){ 
				return BinarySearchHelper(sorted, findMe, low, middle-1); 
			}else{ 
				// findMe > middleElement 
				return BinarySearchHelper(sorted, findMe, middle+1, high); 
			} 
		} 
	} 
}