// BinarySearch.java

public class BinarySearch {

    public static boolean binarySearch(int[] array, int target, int left, int right) {
        if (left > right) {
            System.out.println(target + " was not found.\n");
            return false;
        }

        int middle = (left + right) / 2;
        System.out.println("Search at " + middle);

        if (array[middle] == target) {
            System.out.println("Found " + target + " in slot " + middle + "\n");
            return true;
        } else if (array[middle] < target) {
            return binarySearch(array, target, middle + 1, right);
        } else {
            return binarySearch(array, target, left, middle - 1);
        }
    }

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

    public static void main(String args[]) {
        int nums [] = {2, 7, 13, 22, 30, 35, 36, 42, 44, 48, 53, 56, 60, 67, 68, 73, 77, 78, 84, 89, 91, 95, 99, 100};
        binarySearch(nums, 13);
        binarySearch(nums, 99);
        binarySearch(nums, 40);
    }
}