Missing Number in Sorted Array(N spaces) having values from 0-N

If we want to insert 0-N elements in an array with N spaces, one element will get missed.
e.g For N = 5
input[] 0,1,3,4,5 2 is missing here.

Since we know array is sorted we can do better than O(n), by using Binary Search. If all elements are correctly placed we should get input[index] == index for all elements.

So, if arr[index] == index Search in RIGHT

if arr[index] != index …. Search in LEFT but before going LEFT check if just left is on correct position or not. If just left position is correct, middle is the answer.

Here is the code for this :

public static int findUnMatchedIndex(int[] arr, int start, int end){
        int result;
        if(end - start == 1)
            return arr[end] == end?  (arr[start] == start ? -1:start) : end;
        int middle = (end-start)/2 + start;
        if(arr[middle] == middle)
            result = findUnMatchedIndex(arr,middle+1,end);
        else
            result = (arr[middle - 1] == middle -1) ? middle : findUnMatchedIndex(arr,start,middle-1);
        return result;
    }