Find a missing 32bit integer among a unsorted array containing at most 4 billion ints

Question

Hi,

This is the problem described in Programming pearls. I can not understand binary search method descrbied by the author. Can any one helps to elaborate? Thanks.

EDIT: I can understand binary search in general. I just can not understand how to apply binary search in this special case. How to decide the missing number is in or not in some range so that we can choose another. English is not my native language, that is one reason I can not understand the author well. So, use plain english please:)

EDIT: Thank you all for your great answer and comments ! The most important lesson I leant from solving this question is Binary search applies not only on sorted array!

Answer 1

Well, it's about a file that contains all 4 billion integers except one! That is the catch in this case.

1. As you move along the list of integers, compute the sum.
2. At the end, compute the sum as if there were all integers present using the formula N * (N + 1) / 2
3. Extract the sum at (1) from the sum you computed at (2). That is the missing integer.

Example: Assume we have the following sequence: 9 3 2 8 4 10 6 1 7 (1 through 10 with 5 missing). As we add integers sequentially, we get 9 + 3 + 2 + 8 + 4 + 10 + 6 + 1 + 7 = 50. The sum of all integers from 1 to 10 would be 10 * (10 + 1) / 2 = 55. Therefore, the missing integer is 55 - 50 = 5. Q.E.D.

Answer 2

I believe what the author is getting at is that you pick the midpoint of your current range of integers, and prepare two output files. As you read your input, everything above the midpoint goes into one file, and everything below the midpoint goes into the other.

Once that's finished, you pick whichever of the files is smaller, and then repeat the operation, using [lower bound, midpoint] or (midpoint, upper bound] as your new range, until the file and range are small enough to switch to the bitmap pattern (or one of your output files is empty).

Damien

Answer 3

There is some more information on this web site. Quoted from there:

"It is helpful to view this binary search in terms of the twenty bits that represent each integer. In the first pass of the algorithm we read the (at most) one million input integers and write those with a leading zero bit to one tape and those with a leading one bit to another tape. One of those two tapes contains at most 500,000 integers, so we next use that tape as the current input and repeat the probe process, but this time on the second bit. If the original input tape contains N elements, the first pass will read N integers, the second pass at most N/2, the third pass at most N/4, and so on, so the total running time is proportional to N. The missing integer could be found by sorting on tape and then scanning, but that would require time proportional to N log N."

As you can see, this is a variation on the binary search algorithm: divide the problem into two pieces and solve the problem for one of the smaller pieces.

Answer 4

The general idea is this: pick a range of integers, and select all the integers that fall within that range. If the number of integers is less than the size of your range, you know that that range contains one or more missing numbers.

This applies to the original problem of how you know there are some missing numbers in the first place too.

Answer 5

If you consider numbers in the range from 1 to N; half of them are larger than N/2 and half of them smaller than N/2

The ones larger than N/2 would have the MSB set to one; MSB = 0 for the smaller ones.

Partition the whole set based on MSB which will give you two sets : set of numbers smaller than N/2 and set of number larger than N/2

The partition smaller in size has the missing element.

In the next step, use the next MSB.

1. If the smaller set was less than N/2, half of them are less than N/4 (2nd MSB=0) and the other half larger than N/4 (2nd MSB=1)

2. If the smaller set was larger than N/2, half of them are less than N/2+N/4 (2nd MSB=0) and the other half larger than N/2+N/4 (2nd MSB=1)

Each round will halve the search space and that's it.

 Sum ( N / 2^i ) for 0 <= i < log N gives you O(N)

Answer 6

This is basically the same question as this question. The same approach works here for the ample memory case to get O(N) complexity. Basically just recursively try to put every integer to its correct location and see what doesn't have the correct value.