<p>Here is a way to think about the problem: </p>

<p>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$).</p>

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

<p>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?</p>

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

<p>Is the same as asking "Is $A[\lceil n/2 \rceil] - A[0]&gt; \lceil n/2 \rceil $?"</p>

<p>Can you generalize this to arbitrary lists?</p>

CC BY-SA 3.0
2018-04-29T16:23:11.050Z
2018-04-29T16:23:11.050Z
mm8511
<p>The question is as follows.</p>

<p>Given: A sorted array A of <em>n</em> integers where A[<em>n</em> − 1] − A[0] ≥ <em>n</em>. <br><br>
Asked: Give an algorithm and the invariant of the algorithm that finds a number between A[0] and A[<em>n</em> - 1] that does not appear in the array A. The algorithm must use logarithmic time. <br><br></p>

<p>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. </p>

CC BY-SA 3.0
2018-04-30T08:09:20.633Z
This is not a research-level question, but looks more like homework, it is therefore off-topic here.
Jan Johannsen
<ds.algorithms><search-problem>
Algorithm in logarithmic time that finds a number with the help of a subarray that is not in the array
Jefferson Brian
# Algorithm in logarithmic time that finds a number with the help of a subarray that is not in the array

(Asked by: username_0 on 2018-04-29)

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.

**Tags:** ds.algorithms, search-problem

> **Comments:**
> **username_1**: This is not a research-level question, but looks more like homework, it is therefore off-topic here.  

---

## 1 answers

### Answer by username_2 on 2018-04-29. Score: 0

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?


---

