/**
 * TestBinarySearch.java
 * This program tests out the recursive
 * Binary Search algorithm.
 *
 * Author: Aaron Tan
 */

import java.util.*;

class TestBinarySearch {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int[] intArray = {3, 6, 8, 12, 17, 20, 21, 32, 33, 45};
        System.out.print("Enter search key: ");
        int searchKey = scanner.nextInt();

        int index = binarySearch(intArray, searchKey);

        System.out.println("Key found at index " + index);
    }

    // Returns index of key found, otherwise returns -1
    public static int binarySearch(int[] numbers, int key) {
        return binarySearch(numbers, key, 0, numbers.length-1);
    }

    // Returns index of key found, otherwise returns -1
    private static int binarySearch(int[] numbers, int key,
                                    int low, int high) {
        if (low > high)
            return -1;
        else {
            int mid = (low + high)/2;
            if (numbers[mid] == key)
                return mid;
            else if (numbers[mid] < key)
                return binarySearch(numbers, key, mid+1, high);
            else 
                return binarySearch(numbers, key, low, mid-1);
        }
    }

}