-1
$\begingroup$

The question is as follows.

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

Asked: Give an algorithm and the invariant of the algorithm that finds a number between A[0] 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.

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

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]=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[0]> \lceil n/2 \rceil $?"

Can you generalize this to arbitrary lists?

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.