The interpolation algorithms seem to work quite well when with linear data sets, but throw a non-linear data set at it an it is considerably slower than binary search (see changes below). this produces a set of only 30 numbers, and as you can see from the results below it took 4 times the number of attempts to find (or not find) the number.
unsigned setSize = 70;
unsigned maxValue = 1000000000;
...
...
int main (int argc, char *argv [])
{
dataSet theSet;
unsigned tries;
int theVal, index, tolerance;
unsigned maxRand = (unsigned) sqrt ((double) maxValue);
srand ((unsigned) time (0));
while (true)
{
// Generate dataset
randomFill (theSet, maxValue, setSize);
setSize = theSet.size();
showData (theSet, setSize);
...
...
void randomFill (dataSet& set, unsigned max, unsigned size)
{
unsigned val = maxValue;
set.erase(set.begin(),set.end());
for(unsigned i = 0; i < size && val > 0; i++)
{
set.push_back (val);
val /= 2;
}
// for (unsigned i = 0; i < size; ++i) set.push_back ((rand () * rand ()) % max);
sort (set.begin (), set.end ());
}
Enter a positive integer in the range 0-999999999: 1562500
Enter a tolerance value in the range 0-33333333: 3000
Interpolative search: Determined not to be in set after 21 tries
Binary search: Determined not to be in set after 5 tries
Press ENTER for next iteration
Enter a positive integer in the range 0-999999999: 15625000
Enter a tolerance value in the range 0-33333333: 3000
Interpolative search: Found in element 23 with 24 tries
Binary search: Found in element 23 with 5 tries
Press ENTER for next iteration