find missing element in a sorted array of n element ranges 1 to n without accessing full array

Question

A question asked in Oracle interview "find missing element in a sorted array of n element ranges 1 to n without accessing full array". I am wondering if there is a way to find missing element without accessing all the element ? There is only one element is missing and no repetition. Plz help me if there is a solution to this question .

Answer 1

You do a slightly customized binary search. You access the n/2st element and look at the value. If it is smaller than n/2, your missing element is in the lower half of the array. Else in the upper. Then you do the same in the lower half. And continue that until you are at only one possibility. Works on sorted arrays with random access in O(log(n)).