CODEWITHSUNDEEP
arraysnumbers
Nagendra Yadav
Nagendra Yadav

Reputation: 113

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

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 .

Upvotes: 0

Views: 129

Answers (1)

Lorenz
Lorenz

Reputation: 2269

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)).

Upvotes: 2

Related Questions