package search;

public class BinarySearchMissing {
    public static void main(String[] args) {
        int x = getArgument(args);
        int[] array = getArray(args);
        System.out.println(binarySearchRecursive(array, x) & binarySearchIterative(array, x));
    }

    private static int binarySearchIterative(int[] array, int value) {
        int l = 0, r = array.length;
        int m;
        while (l < r) {
            m = (l + r) / 2;
            if (array[m] > value) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return getPosition(array, r, value);
    }

    private static int binarySearchRecursive(int[] array, int value) {
        int l = 0, r = array.length;
        if (l == r) {
            return -1;
        }
        int m = (l + r) / 2;
        if (value >= array[m]) {
            return binarySearchRecursive(array, value, l, m);
        } else {
            return binarySearchRecursive(array, value, m + 1, r);
        }
    }

    private static int binarySearchRecursive(int[] array, int value, int l, int r) {
        if (!(l < r)) {
            return getPosition(array, r, value);
        }
        int m = (l + r) / 2;
        if (value >= array[m]) {
            return binarySearchRecursive(array, value, l, m);
        } else {
            return binarySearchRecursive(array, value, m + 1, r);
        }
    }

    private static int getPosition(int[] array, int pos, int value) {
        if (pos < array.length && array[pos] == value) {
            return pos;
        } else {
            return -pos - 1;
        }
    }

    private static int getArgument(String[] array) {
        return Integer.parseInt(array[0]);
    }

    private static int[] getArray(String[] array) {
        int[] result = new int[array.length - 1];
        for (int i = 0; i < array.length - 1; i++) {
            result[i] = Integer.parseInt(array[i + 1]);
        }
        return result;
    }
}