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!

Geostrophic

Which part do you not understand? Can you elaborate? – Copperplate

Binary search is the solution for another problem. It's not suitable to find a value in an unsorted range. – Vespucci

What you can't understand? Binary search at all or just authors description? – Digitalin

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. – Digitalin

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. – Warbler

I believe this problem isn't that only one of the integers is missing (the description states that there are at most 4 million integers in the file) – Semifinalist

@Nikolai: Actually, for this specific problem (concerning integers) you can use a binary search algorithm, see my answer. – Volition

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.

Volition

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) – Fret

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)). – Volition

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. – Gunny

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. – Volition

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) – Celibacy

rwwilden: if you double the size of your data, the time taken to do a complete pass doubles. therefore O(n) is a strict lower bound on your running time. for an analogy, consider finding the maximum element in an array. the algorithm is simply "take a complete pass through the data, recording the highest value you see". this algorithm doesn't change no matter how large your array is; there is just one "step", but the complexity is O(n). – Gunny

Ok, I stand corrected and I think you are right and I'm wrong. Thanks for following up on my post. – Volition

@RonaldWildenberg, I don't quite understand how the binary search works. Do you mean that, first read those numbers with a leading zero into file a, then read those with leading one into file b. second, count a and b to find how many numbers in each file, if one file's count is less than 500,000 then the missing number gotta be in range of that file. Am I right? – Melodie

@RonaldWildenberg The link you provided doesn't work now. Can you provide a working link please? – Manassas

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

Semifinalist

By what criterium do you select an upper half and a lower half? Since the elements are unsorted. – Volition

@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) – Semifinalist

@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. – Semifinalist

@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? – Melodie

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.

Gunny

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)

Butterfield

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.

Pina

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.

Rasberry

No, it's an unsorted range. However, you're correct that there's more than one gap (problem says at most 4 billion integers) – Semifinalist

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. – Gunny

(sorry about the deleted reply, i misread the problem too the first time around) – Gunny

This is a solution to the problem. However, it doesn't scale very well and doesn't use a binary search as was asked. – Volition

as nikolai pointed out in the comments on the problem, the binary search has nothing to do with the problem; it's the next chapter in the book, which the op mistook for a continuation of the questions in the first chapter. – Gunny

gah, nevermind, i need more coffee :) the binary search is indeed both relevant and intended. – Gunny

the running sum, and the target number N(N+1)/2 will need to be kept in 64 bits. – Knives

You need to read the question once again. (No one said that there is ONLY one number missing - at least one number means something different) Atmost 4 billion would leave at least 294967296 integers missing. [2^32 - 1 - (4 * 10^9)] N*(N+1)/2 - YourSum will give a huge number which is the sum of the all the missing ones. In your case. Assuming 5 and 6 were the missing ones, you will get a difference of 11, which could be 9+2 or 8+3 or 7+4 or 5+6; How to proceed? – Butterfield