algorithm - Find the first "missing" number in a sorted list

Question

Let's say I have the continuous range of integers [0, 1, 2, 4, 6], in which the 3 is the first "missing" number. I need an algorithm to find this first "hole". Since the range is very large (containing perhaps 2^32 entries), efficiency is important. The range of numbers is stored on disk; space efficiency is also a main concern.

What's the best time and space efficient algorithm?

Answer 1

Use binary search. If a range of numbers has no hole, then the difference between the end and start of the range will also be the number of entries in the range.

You can therefore begin with the entire list of numbers, and chop off either the first or second half based on whether the first half has a gap. Eventually you will come to a range with two entries with a hole in the middle.

The time complexity of this is O(log N). Contrast to a linear scan, whose worst case is O(N).