Efficient Numerical Search

[oconman]

I have been facing a problem developing an algorithm for an efficient numerical search. The scope of the problem is such: you have a sequence of numbers 1 - 1000 ,for example, one of the values is missing but you don't know which one. The problem is in designing an efficient algorithm that will identify the missing value. I have considered variation on a binary search technique but so far no luck. Any suggestions.

Thanks

 

[mseth]

How is the data given to you, is it pre-sorted?

 

[oconman]

Read in from a file either flat file or db. I was thinking of reading into an array and then performing some sort of binary search. The key to the problem is obviously you don't know the missing number but it is within a sequence of number ascending by one ie. 23, 24, 25, 27,28 just for example. Now if this sequence is in a sequence of lets say 10000 records or maybe 10000000 I am trying to come up with a search algorithn that will perform better than linear time.

Alternatively what about a graph where each node is a number with two edges one to number below the other to number above so from the above node 24 would have 2 edges one to 23 one to 25, however 25 would only have one edge to 24, meanwhile 27 only one edge too, to 28. But I am not sure if this would be better than linear time.

Any suggestions appreciated

Thanks

 

[xwb]

Why not store the missing numbers and look for them instead and remove them as you find them.

 

[cpjust]

Assuming all the numbers are sorted, why not do something like this:

1. If # of elements in array < highest number then there are (Highest number - Array elements) missing numbers.

2. Move to the middle array element. If the number != array index + 1, there are numbers missing in the bottom half. Keep dividing it in half and comparing the number to the array index to find the missing numbers.
Find the lowest missing number first, then move up and adjust the array index to compensate for the missing numbers when you do the comparisons...

 

[tokra]

If you know beforehand the size of the list and that all numbers are expected to be consecutive...

here are some uncompiled ideas
this one finds the sum of all the numbers in the series and then subtracts all the values from it. whats left is what we are missing

unsigned int findmissing(unsigned int low,unsigned int high,unsigned int *list)
{
unsigned long pairsum(low+high);
unsigned long numpairs((high-low+1)/2);//We are counting on trucation
unsigned long sum(pairsum*numpairs);//Sum off all numbers in seires
if ((high-low+1)%2) //what about the number in the middle of there are an odd number of values in the seiries
{
sum=low*numpairs;//middle number
}
for (int i=0;
i<(high-low);//we want one less than the number to avoid buffer issues
i++)
{
sum-=list[i];
}
return sum;
}

This one is slightly more practicle and less esoteric. It fills an array of bool with falses and sets the index of each value to true whats false is whats left.

int findmissing(int low,int rangesize,int *list)
{
bool thearray=new bool[rangesize];
int i;
for (i=0;i<rangesize;i++)
{
thearray[i]=false;
}
for (i=0;i<rangesize-1;i++)
{
thearray[list[i]]=true;
}
for (i=0;i<rangesize;i++)
{
if (!thearray[i]) return i;
}
throw;//we are NOT supposed to make it here
return -1;
}

WR

 

[Zyrenthian]

To add all numbers 1 to n you can calculate it without a for loop by doing

int quickSum = (sumTo+1)*(sumTo/2) + ((sumTo+1)/2) * (sumTo%2);

Where sumTo in your case is equal to 1000

Now, take your array with one missing number, sum it and subtract it from quickSum... You have your missing number.

Matt

 

[jstreich]

Binary search won't work, because you have no way of knowing if the missing number is smaller or larger. The problem is O in the number of elements if you are checking a sorted array.... I'd do it this way to start out with:

const int n = 1000;
bool arr[n];
for(int i = 0; n > i; ++i)
  arr[i] = false;
int val; 
while( /*get data into an int val*/ )
{
  arr[val-1] = true;
}
for(int i = 0; n > i; ++i)
  if(!arr[i]) break;
if(n <= i)
  cout << "all here!";
else
  cout << i+1 << " is missing.";

Looking at the post above this one, If know your range, you can hardcode in the sum of all numbers 1 to n... If you don't remember this proof:

n
___
\ i = (n*(1+n))/2
/__
i=1

So, your code would be something like:

int sum = 0;
int num;
while( /* read an num */ )
{
   sum += num;
}
num = sum - (1000+1001)/2;