# Algorithm in logarithmic time that finds a number with the help of a subarray that is not in the array

The question is as follows.

Given: A sorted array A of n integers where A[n − 1] − A ≥ n.

Asked: Give an algorithm and the invariant of the algorithm that finds a number between A and A[n - 1] that does not appear in the array A. The algorithm must use logarithmic time.

I have no idea how to approach the problem and what the steps are that I need to take/think of. I think it has something to do with binary search but didn't get any further than that.

• This is not a research-level question, but looks more like homework, it is therefore off-topic here. – Jan Johannsen Apr 30 '18 at 8:09

Here is a way to think about the problem:

We will deal with a slightly simplified version, but it should be easy for you to generalize. Assume that $A=0$ and $A[n-1]=n$, and let $i^{*}$ be the unique index of $A$ such that $A[i^{*}]-A[i^{*}-1] \geq2$ (here we assume there is only one element in the range {$0,1,\dots,n$} that is not in $A$).

Look at the median value of A suppose that $A[\lceil n/2 \rceil]> \lceil n/2 \rceil$ what does this tell you about $i^{*}$ Is it possible that $i^{*}$ is in the latter half of $A$?

Alternatively, suppose that $A[\lceil n/2 \rceil]= \lceil n/2 \rceil$ (this is the only other option based on our assumptions on $A$). Is it possible that $i^*$ is in the first half of the array?

Note that, in this case, asking "Is $A[\lceil n/2 \rceil]> \lceil n/2 \rceil$?"

Is the same as asking "Is $A[\lceil n/2 \rceil] - A> \lceil n/2 \rceil$?"

Can you generalize this to arbitrary lists?