public class FixedPoint {

    // 1064: Fixed Point

    /*
    Given an array of n distinct integers sorted in ascending order,
    write a function that returns a Fixed Point in the array,
    if there is any Fixed Point present in array, else returns -1.

    Fixed Point in an array is an index i such that arr[i] is equal to i.
    Note that integers in array can be negative.
    */

    int binarySearch(int[] arr, int low, int high) {
        if (high >= low ){
            int mid = (low + high) / 2;

            if (arr[mid] == mid)
                return mid;

            if (arr[mid] > mid)
                return binarySearch(arr, low, mid -1);

            return binarySearch(arr, mid + 1, high);
        }
        return -1;
    }

    public static void main(String[] args) {
        FixedPoint fx = new FixedPoint();
        int[] arr = {-1, 0, 2, 4, 9};
        int n = arr.length;

        int result = fx.binarySearch(arr, 0, n - 1);
        System.out.println(result);
    }

}