Analysis of Algorithms - Find missing Integer in Sorted Array better than O(n)

Question

I am working through analysis of algorithms class for the first time, and was wondering if anyone could assist with the below example. I believe I have solved it for an O(n) complexity, but was wondering if there is a better version that I am not thinking of O(logn)?

Let A= A[1] <= ... <= A[n+1] be a sorted array of n distinct integers, in which each integer is in the range [1...n+1]. That is, exactly one integer out of {1,...,n+1} is missing from A. Describe an efficeint algorithm to find the missing integer. Analyze the worst case complexity (number of accesses to array A) of your algorithm.

The solution I have is relatively simple, and I believe results in a worst case N complexity. Maybe I am over thinking the example, but is there a better solution?

My Solution

for(i = 1; i < n +1; i++) :
    if(A[i-1] > i) :
         return i

The logic behind this is since it is sorted, the first element must be 1, the second must be 2, and so on and so forth, until the element in the array is larger than the element it is supposed to be, indiciating an element was missed, return the element it should be and we have the missing one.

Is this correct logic? Is there a better way to go about it?

Thanks for reading and thanks in advance for the assistance.

Answer 1

This logic is certainly correct, but it is not fast enough to beat O(n) because you check every element.

You can do it faster by observing that if A[i]==i, then all elements at j < i are at their proper places. This observation should be sufficient to construct a divide-and-conquer approach that runs in O(log₂n):

• Check the element in the middle
• If it's at the wrong spot, go left
• Otherwise, go right

More formally, you are looking for a spot where A[i]==i and A[i+1]==i+2. You start with the interval at the ends of the array. Each probe at the middle of the interval shrinks the remaining interval twofold. At some point you are left with an interval of just two elements. The element on the left is the last "correct" element, while the element on the right is the first element after the missing number.

Answer 2

You can binary search for the first index i with A[i] > i. If the missing integer is k, then A[i] = i for i < k and A[i] = i + 1 for i >= k.