How to find a missing number if a range of millions of numbers in an array?
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
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.