Re: Algorithm to find break in contiguity

From: use...@xxxxxxxxxxxxxxx
I need an efficient algorithm for the following problem:
If you have unique N-1 numbers in the range 1 to N, find the
missing number.

What's best depends almost entirely on how your original data is
given to you. If it's stored in a disk file, you probably can't
save any significant time by jumping around doing a binary search,
best to just read the whole file sequentially, but in that case you
might as well compare each pair of adjacent numbers (or checking
each number individually against what's expected at that spot if
the missing number hasn't been reached yet) as you are reading.
With buffered I/O, you will probably spend most of your time
finished checking the current block and waiting for the next block
to load. That's assuming the numbers are stored in ascending
sequence.

If the data is stored sequentially in a array, or some sort of
balanced binary tree, you can do a binary search to find where the
jump over the missing number occurs.

If the data is stored sequentially in a linked-list, the answer
depends on whether it's small enough to be mapped into RAM at the
same time, in which case sequential scan down the links is optimal,
or whether it's so huge that sequential scan down the links would
thrash virtual memory, in which case it's a much more difficult
problem to solve.

If the data is not already in sequence, that's a whole 'nother problem.
You didn't state the problem clearly enough to know where you're
getting your data from in what sequence in what form.
Since you used the word "contiguity" in the Subject field, I
*assume* the data is in ascending or descending sequence in either
contiguous memory (disk file or array) or at least logically
contiguous (linked list or binary tree), but that might not have
been correct.
.

Relevant Pages

  • Re: Programmers unpaid overtime.
    ... "A polynomial is a mathematical expression involving ... And if terms are missing, or the exponents are out of sequence, the ... You all think I'm paranoid, ...
    (comp.programming)
  • Re: puzzle
    ... Determine the xor of the numbers 0...n, ... >) sequence. ... Determine the sum of the numbers 0...n, ... The difference of the two sums is the missing number. ...
    (comp.programming)
  • Re: Query to find amissing number
    ... Here I need to write a query to find out that number 7 is missing in the ... given sequence. ... giving you a quick way to determine if any gaps exist. ...
    (comp.databases.sybase)
  • Re: Find Missing Numbers in a Sequence
    ... This will list the start of the gap. ... The simplest solution to catch every item that is missing would be ... to use an auxiliary table that contains nothing but a sequence of numbers ... numerical order, is there a way to create a query that will return a ...
    (microsoft.public.access.queries)
  • Re: puzzle
    ... Determine the xor of the numbers 0...n, ... sequence. ... Determine the sum of the numbers 0...n, ... The difference of the two sums is the missing number. ...
    (comp.programming)