/*
 * T12n04.java:  Iterative and Recursive versions of Binary Search.
 *
 * Be sure to read the comment ahead of the recursive version.
 */

import java.util.*;

public class T12n04
{

        /*
         * binSearchIterative() -- Searches the given array for the given
         *   target using an iterative implementation of binary search.
         *
         *   Precondition:  searchMe is sorted in ascending order
         *   Postcondition: true returned if target found; false o.w.
         */

    public static boolean binSearchIterative(int [] searchMe, int target)
    {
        int low = 0, high = searchMe.length-1, mid;

        while (low <= high) {
            mid = (low + high) / 2;
            if (searchMe[mid] == target)
                return true;
            if (searchMe[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return false;
    }


        /*
         * binSearchRecursive() -- Searches the given array for the given
         *   target using a recursive implementation of binary search.
         *
         *   You might note that we have two versions of this even though
         *   we aren't in an instantiable class.  This time the reason is
         *   the need to change the search range endpoints with each call.
         *   There's no reason to force the programmer to give us the
         *   search range; all we need is the array and the target.
         *
         *   And, of course, this could be generalized to work with an
         *   array of Comparable objects.
         *
         *   Precondition:  searchMe is sorted in ascending order
         *   Postcondition: true returned if target found; false o.w.
         */

    public static boolean binSearchRecursive(int [] searchMe, int target)
    {
        return binSearchRecursive(searchMe,target,0,searchMe.length-1);
    }

    public static boolean binSearchRecursive(int [] searchMe, int target,
                                             int low, int high)
    {
        if (low > high)        // Base Case: No sublist left to search
            return false;
        else {                 // General Case
            int mid = (low + high) / 2;
            if (searchMe[mid] == target)
                return true;
            if (searchMe[mid] < target)
                return binSearchRecursive(searchMe,target,mid+1,high);
            else
                return binSearchRecursive(searchMe,target,low,mid-1);
        }
    }


    public static void main (String [] args)
    {
        int [] searchMe = {3,4,6,9,10,11,14,18,34,49,50,56,65,68,71,72,78};

        System.out.println("\nThe list to be searched:");
        System.out.print("\t");
        for (int i=0; i<searchMe.length; i++) {
            System.out.print(searchMe[i] + " ");
        }
        System.out.println();

        int [] target = {68,3,17,-5,365};      // our test cases

        for (int i=0; i<target.length; i++) {

            System.out.println("\nSearching for " + target[i] 
                             + " using iterative binary search: " 
                             + binSearchIterative(searchMe,target[i]));

            System.out.println("Searching for " + target[i] 
                             + " using recursive binary search: " 
                             + binSearchRecursive(searchMe,target[i]));
        }

    }
}