FindMissingNumber.java

    //I/P    [1, 2, 4, ,6, 3, 7, 8]
    //O/P    5

    //NOTE : array is sorted
    //1 .total = n*(n+1)/2 leads to overflow if total can't be represented by the number O(n)
    //2. XOR (given array) ^ (numbers from 1-n) = missing number  O(n)
    //3. Binary search (Find out the hole wheather in first half/second half) (O log n)

    //Array: [1,2,3,4,5,6,8,9]
    //Index: [0,1,2,3,4,5,6,7]

    public static int binarySearchHelper(int a[],int start,int end) {
        if (start < end) {
            int mid = start + (end - start) / 2;
            if (a[mid] - a[start] != (mid - start) ) {
                //hole is in first half
                if (mid - start == 1 && a[mid] - a[start] != 1) {
                    return mid;
                } else {
                    return binarySearchHelper(a,start,mid-1);
                }
            } else if (a[end]-a[mid] != (end-mid) ) {
                //hole is in second half
                if (end - mid == 1 && a[end] - a[mid] != 1) {
                    return mid;
                } else {
                    return binarySearchHelper(a,mid+1,end);
                }
            } else {
                return -1;
            }
        } else {
            return -1;
        }
    }

    public static int findMissingNumber (int a[]) {
        int len = a.length;
        return binarySearchHelper (a,0,len);
    }