Algorithm Analysis - Finding the missing integer in a sorted array is better than O (n)

Question

This is the first time I am working on an analysis of a class of algorithms and am wondering if anyone can help in the example below. I believe I solved this for O (n) complexity, but wondered if there is a better version that I don't think about (logn) about?

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

The solution that I have is relatively simple, and I believe that the results are in the worst case complexity N. Maybe I'm already thinking about this example, but is there a better solution?

My decision

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

The logic behind this is that since it is sorted, the first element should be 1, the second should be 2, etc. etc., while the element in the array is larger than the element that it should be, the element indication was omitted, return the element that it should be, and we have the missing one.

Is this the correct logic? Is there a better way to do this?

Thank you for reading and in advance for your help.

Answer 1

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

You can do this faster by noticing that if A[i]==i , then all elements in j < i are in their places. This observation should be enough to build a divide and conquer approach that works in O (log ₂ n):

• Check the item in the middle
• If it's not in that place, go left
• Otherwise, act correctly.

More formally, you are looking for a place where A[i]==i and A[i+1]==i+2 . You start with an interval at the ends of the array. Each probe in the middle of the interval halves the remaining interval by half. At some point, you are left with an interval of two elements. The element on the left is the last "correct" element, and 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 k, then A [i] = i for i <k and A [i] = i + 1 for i> = k.

Answer 3

Sometimes the trick is to think differently about the problem.

In the spirit, you just work with an array of booleans; the record with index n is true a[n] > n .

In addition, this array starts from zero or more consecutive false , and the remaining entries are all true .

Now your problem is to find the index of the first true instance in the (sorted) array of booleans.