## How to find a missing number if a range of millions of numbers in an array?

Problem Description:

I want to get the *first* missing number in a range of millions of numbers. For example, I have an array with `n`

number of elements. And it starts from 0. And in between for example, after 4380, 4381 is missing and is continued with 4382. So, how can I find that 4381?

I have seen this questions on many sites including SO, Quora and many more. But, all I could find was with a small range of numbers. For which, a for loop is the best choice. But, when we have millions of numbers in an array, then this wont be both time and memory efficient. What can be used in this case to get it done having both the time and memory in consideration?

**NOTE:** The elements are ordered in ascending order

## Solution – 1

So when you have a sorted array of `n`

elements starting at `0`

then there is a clear correlation between an element’s index and value (assuming there can be no duplicates):

```
index value
0 0
1 1
2 2
...
100 100
```

So you can use a binary-search approach and check e.g. the element at `length / 2`

. If the value is greater than its index, there has to be a missing number somewhere below.

```
index value
0 0
1 1
2 2
...
100 100
101 102
102 103
...
204 205
```

In this example, if you would check index `102`

you would see a value of `103`

, so between index `0`

and `102`

there has to be a missing number. Now, repeat the algorithm for the sub-array `0..101`

until you have found the missing element. Otherwise, proceed with the other half.

If elements do not start at `0`

it would be easy to add a constant value everywhere.

If there can be arrays *without* a missing number, you can also start by comparing the last element and abort immediately if the value is equal to its index.