public class BinarySearch {
    /**
     * Search the given array for the given integer using a binary
     * search. This method assumes that the elements in the array
     * are stored in order. If the element is found, the method
     * returns the position of the element, otherwise it returns -1.<p>
     *
     * @param array  The array of integers to search<p>
     * @param target The integer to search for<p>
     *
     * @return target's position if found, -1 otherwise
     *
     */

    public static int binsearch(int[] array, int target)    {

	int start = 0;               // The start of the search region
	int end   = array.length - 1;// The end of the search region
	int position = -1;           // Position of the target

	// While there is still something list left to search and
	// the element has not been found
	while (start <= end && position == -1)	{
	  int mid = start + (end - start) / 2;
	  //	    int mid = (start + end) / 2;  // Location of the middle

	    // Determine whether the target is smaller than, greater than,
	    // or equal to the middle element
	    if (target < array[mid])   {
		// Target is smaller; continue the left half
		end = mid - 1;
	    }
	    else if (target > array[mid])  {
		// Target is larger, continue the right half
		start = mid + 1;
	    }
	    else  {
		// Found it!
		position = mid;
	    }
	}
	
	// Return the location of the target
	// Could be -1 if not found
	return position;
    }

    /**
     * Search the given array for the given integer using a binary
     * search. This method assumes that the elements in the array
     * are stored in order. If the element is found, the method
     * returns the position of the element, otherwise it returns -1.<p>
     *
     * @param array  The array of integers to search<p>
     * @param target The integer to search for<p>
     *
     * @return target's position if found, -1 otherwise
     *
     */

    public static int binsearchRecursive(int[] array, int target,
					 int start, int end)    {

	int position = -1;           // Position of the target

	if (start <= end) {
	  int mid = start + (end - start) / 2;
	  //	    int mid = (start + end) / 2;  // Location of the middle
	    
	    // Determine whether the target is smaller than, greater than,
	    // or equal to the middle element
	    if (target < array[mid])  {
		// Target is smaller; continue the left half
		position = binsearchRecursive(array, target, start, mid - 1);
	    }
	    else if (target > array[mid])  {
		// Target is larger, continue the right half
		position = binsearchRecursive(array, target, mid + 1, end);
	    }
	    else  {
		// Found it!
		position = mid;
	    }
	}
	    
	// Return the location of the target
	// Could be -1 if not found
	return position;
    }


    /**
     * The method <code>testBinarySearch</code> tests the binary search method
     * for an given array. We search the values at the boundary of the array
     * as well as a non-existing value in the array.<p>
     *
     * @param numbers an <code>int[]</code> value which is the given array.<p>
     */
    public static void testBinarySearch(int[] numbers) {

	System.out.println("Search for 16, location should be at 4, "
			   + " found at " + binsearch(numbers, 16));
	System.out.println("Search for 196, location should be at 14, "
			   + " found at " + binsearch(numbers, 196));
	System.out.println("Search for 0, location should be at 0, "
			   + " found at " + binsearch(numbers, 0));
	System.out.println("Search for 361, location should be at 19, "
			   + " found at " + binsearch(numbers, 361));
	System.out.println("Search for 15, location should be at -1, "
			   + " found at " + binsearch(numbers, 15));
    }

    /**
     * The method <code>testBinarySearch</code> tests the binary search method
     * for an given array. We search the values at the boundary of the array
     * as well as a non-existing value in the array.<p>
     *
     * @param numbers an <code>int[]</code> value which is the given array.<p>
     */
    public static void testRecursiveBinarySearch(int[] numbers) {

	System.out.println("Search for 16, location should be at 4, "
			   + " found at " 
			   + binsearchRecursive(numbers, 16, 0, numbers.length - 1));
	System.out.println("Search for 196, location should be at 14, "
			   + " found at " 
			   + binsearchRecursive(numbers, 16, 0, numbers.length - 1));
	System.out.println("Search for 0, location should be at 0, "
			   + " found at " 
			   + binsearchRecursive(numbers, 16, 0, numbers.length - 1));
	System.out.println("Search for 361, location should be at 19, "
			   + " found at " 
			   + binsearchRecursive(numbers, 16, 0, numbers.length - 1));
	System.out.println("Search for 15, location should be at -1, "
			   + " found at " 
			   + binsearchRecursive(numbers, 16, 0, numbers.length - 1));
    }


  /**
   * Use binary search to find a proper place to insert a new number.<p>
   * The new number should be inserted after this location.<p>
   *
   * @param array the data collection
   * @param target the new number to be inserted
   */
    public static int binsearchForInsertion(int[] array, int target)    {

	int start = 0;               // The start of the search region
	int end   = array.length - 1;// The end of the search region
	int position = -1;           // Position of the target

	// While there is still something list left to search and
	// the element has not been found
	while (start <= end && position == -1)	{
	  int mid = start + (end - start) / 2;
	  //	    int mid = (start + end) / 2;  // Location of the middle

	    // Determine whether the target is smaller than, greater than,
	    // or equal to the middle element
	    if (target < array[mid])   {
		// Target is smaller; continue the left half
		end = mid - 1;
	    }
	    else if (target > array[mid])  {
		// Target is larger, continue the right half
		start = mid + 1;
	    }
	    else  {
		// Found it!
		position = mid;
	    }
	}

	if (position == -1) { // the target is not in, find the position
	                      // to insert
	  position = start;
	  while (position < end && array[position] < target)
	    position ++;
	  position --; // insert after the position
	}

	return position;
    }


    /**
     * The method <code>testBinarySearchForInsertion</code> tests 
     * the binary search for insertion method
     * for an given array. 
     *
     * @param numbers an <code>int[]</code> value which is the given array.<p>
     */
    public static void testBinarySearchForInsertion(int[] numbers) {

	System.out.println("Search for 15, location should be at 3, "
			   + " found at " 
			   + binsearchForInsertion(numbers, 15));
	System.out.println("Search for 197, location should be at 14, "
			   + " found at " 
			   + binsearchForInsertion(numbers, 197));
	System.out.println("Search for 363, location should be at 19, "
			   + " found at " 
			   + binsearchForInsertion(numbers, 363));
	System.out.println("Search for -1, location should be at -1, "
			   + " found at " 
			   + binsearchForInsertion(numbers, -1));
    }


    public static void main(String[] args)  {

	int size = 20;
	int[] numbers = new int[size];

	// Generate the array
	for (int i = 0; i < size; i ++)
	    numbers[i] = i * i;   // Square it!

	System.out.println("Testing binary search ... in the range (0 - " 
			   + ((size - 1) * (size - 1)) + ")");
	testBinarySearch(numbers);

	System.out.println("\n=========================\n");

	System.out.println("Testing recursive binary search ... in the range (0 - " 
			   + ((size - 1) * (size - 1)) + ")");
	testBinarySearch(numbers);

	System.out.println("\n=========================\n");

	System.out.println("Testing binary search for insertion... in the range (0 - " 
			   + ((size - 1) * (size - 1)) + ")");
	testBinarySearchForInsertion(numbers);

	

    }
}