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.

• aquinas: Yes. There is a better solution. Hint: do you REALLY have to look at every element in the array?
• Scott - Слава Україні: Would you please clean up your statement of the problem? (1) If the A’s are distinct, that means they aren’t equal; so why not just say "A[1] < A[2] < ..."? (2) If { A[1], A[2], ..., A[n+1] } ⊆ { 1, 2, ..., n+1 }, then, ∀i, A[i] = i, and so there is no missing integer. Your text says "n distinct integers", so it can’t be A[1], A[2], ..., A[n+1]. (3) Your problem statement says that the A’s begin with A[1], but your solution starts at A[0] (and, in the comments, you say that the array indices start at [0]).

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.

• Busturdust: Let me take a shot at turning this into english based : - Pick the middle Value of 1....N - If A[i-1] (since valid integers start at 1, and array access starts at 0) != i - The missing element must be in the left - Pick the middle of 1 .... I-1 Rinse repeat until A[i-1] > i does this work?
• Busturdust: and if original pick was A[i-1] == i, then do the same to the right
• Sergey Kalinichenko: @Busturdust Yes, that's it.
• Busturdust: Is A[i-1] > i really the termination clause? Because say if the element missing is the 1, all elements will be A[i-1] > i, and will terminate previously to getting to the first element. I think im missing something
• Sergey Kalinichenko: @Busturdust You need to find a spot where A[i]==i and A[i+1]==i+2. You start with the interval at the ends of the array, and 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.

Answer 3

Sometimes the trick is to think of the problem in a different way.

In spirit, you are simply working with an array of boolean values; the entry at index n is the truth of a[n] > n.

Furthermore, this array begins with zero or more consecutive false, and the remaining entries are all true.

Your problem, now, is to find the index of the first instance of true in the (sorted) array of boolean values.