package binary_search;

public class binary_search
{

    public static void main(String[] args)
    {
        int[] arr = new int[20];
        for (int i = 0; i < 20; i++)
        {
            arr[i] = i + 1;
        }

        int index = search(arr, 17);
        System.out.println(index);
    }

    // Just a wrapper to the binary search.
    private static int search(int[] arr, int value)
    {
        return binarySearch(arr, 0, arr.length - 1, value);
    }

    /**
     * Recursive implementation of binary search in a integer array. Search has a
     * O(log n) time complexity.
     *
     * @param arr
     * @param low
     * @param high
     * @param value
     * @return
     */
    private static int binarySearch(int[] arr, int low, int high, int value)
    {
        int mid = low + (high - low) / 2;
        if (arr[mid] == value)
        {
            return mid;
        }

        // If the value is less than the mid point search the first half
        if (arr[mid] > value)
        {
            return binarySearch(arr, low, mid - 1, value);
        }
        // If the value is greater than the mid point than search the last half of the
        // array.
        if (arr[mid] < value)
        {
            return binarySearch(arr, mid + 1, high, value);
        }

        // If it isn't in the arr return -1
        return -1;
    }

}