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

Question

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!

• dirkgently: Which part do you not understand? Can you elaborate?
• Nikolai Ruhe: Binary search is the solution for another problem. It's not suitable to find a value in an unsorted range.
• Ilya Khaprov: What you can't understand? Binary search at all or just authors description?
• Ilya Khaprov: if array unsorted. We can sort an array nlog(n) (well, somtimes we can sort it with O(n)) then do binary search log(n) this is by 2log(n) times bore then the worst case of sequential search.
• sisve: Your problem description sounds like you have all numbers 0-2^32-1 with the exception of one number that is missing. Assuming that case and you could find the number that's missing by calculating the sum of all numbers that should be there (this is static) and comparing with the sum of the numbers you actually have.

Answer 1

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.

• Matthieu M.: If I remember correctly, 1 + 1/2 + 1/4 .. = Sum(1/2^n) tends towards 2. Therefore this approach as a complexity of O(2N)
• Ronald Wildenberg: That is not true. The complexity is actually O(log n). Suppose the problem space is 8 (so we need to find a missing integer in the range 0,1,2,3,4,5,6,7). This requires at most 3 passes of the algorithm. If we double the problem space to 16, we require at most 4 passes of the algorithm. So although the problem space has doubled from 8 to 16, the time it takes to solve the problem has only increased by a factor 1.33333... If we double up again, the time it takes to solve the problem increases only by a factor 1.25. Which means that the complexity of the algorithm is not linear (so not O(2n)).
• Martin DeMello: The minute we've taken one complete pass through the data, the complexity is O(n), so O(log(n)) is right out. Now O(n) means that there is some constant, c, such that the running time of the algorithm is bounded from above by c*n, so O(2n) is exactly the same as O(n). rwwilden, your mistake was in only counting passes when the value of a pass also doubles.
• Ronald Wildenberg: But you should take the complete algorithm into account. One step involves (pass through data, divide in two, choose left/right). Solving the entire problem involves taking multiple of these steps. As n increases, the number of steps to take doesn't increase linearly along with it. So the complexity does not increase linearly with n. The fact that within a step you need to do an complete pass through the data doesn't change that. The complexity may not be O(log n), but I'm pretty sure it's not linear.
• Dolphin: It is exactly linear. Look at the sum Matthieu posted. The first pass is N, seconds pass is .5n, third pass is .25n and so on. The actual number of operations would be 2N-2, which is O(N)

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

• Ronald Wildenberg: By what criterium do you select an upper half and a lower half? Since the elements are unsorted.
• Damien_The_Unbeliever: @rwwilden - I'm not sure I understand your query? If you're asking which half you continue to work with, I believe I answered that (the smaller file, which was indicated in the problem text)
• Damien_The_Unbeliever: @rwwilden - I think I may have been unclear - when I was talking about range, and midpoint, I was referring to the numerical values, not their position in the input file. We essentially posted the same description.
• Alcott: @Damien_The_Unbeliever, according to the post, we just know just know there are 4 billion ints, so how could we figure out the middle point of the range? 2^32 / 2?

Answer 3

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 4

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 5

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.

Answer 6

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.

• Damien_The_Unbeliever: No, it's an unsorted range. However, you're correct that there's more than one gap (problem says at most 4 billion integers)
• Martin DeMello: it's about a file that contains at most 4 billion integers (it could contain fewer), which is of course not the entire range of int32. you have to find at least one of the 32 bit integers that aren't in the file.
• Martin DeMello: (sorry about the deleted reply, i misread the problem too the first time around)
• Ronald Wildenberg: This is a solution to the problem. However, it doesn't scale very well and doesn't use a binary search as was asked.
• JustJeff: the running sum, and the target number N(N+1)/2 will need to be kept in 64 bits.