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

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

Contents

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.

Rate this post
We use cookies in order to give you the best possible experience on our website. By continuing to use this site, you agree to our use of cookies.