Interpolationsearch unknown Bug

General Discussions
#1

Hello,
well nothing directly about Game dev, but hopefully someone can help me.
I tried to implement Interpolationsearch, but it´s not working properly and even after Debugging I have no clue where my fault is.

 private int interpolationSearch(int[] data, int toSearch, int left, int right) {
        int pivot = left + ((toSearch - data[left]) / (data[right] - data[left])) * (right - left);
        if (pivot < 0 || pivot >= data.length) return -1;
        if (data[pivot] == toSearch) return pivot;
        if (data[pivot] < toSearch) {
            return interpolationSearch(data, toSearch, pivot + 1, right);
        } else if (data[pivot] > toSearch) return interpolationSearch(data, toSearch, left, pivot - 1);
        return -1;
    }

My Problem is that with special Numbers i get negative pivots.
I thought it´s about JAVAs int size but even after I used BigInteger or double I get wrong ones.

Second, if I have “normal” numbers. It´s not working as Interpolationsearch, but as “linear search” - so my pivot begins from 0 and goes to array length.

{5, 3, 5, 228, 14, 69, 18, 27, 109, 85}; becomes an linear search and
{-2074115388, -1899117555, -1339377864, -1242732811, -957055745, 209856485, 632141739, 826711003, 1894825342, 1968537296}, return an negative pivot

Anyone can please help me?

#2

Correct me if I’m wrong, but I thought that interpolation search was for sorted arrays?

#3

Indeed.

#4

Yes, it is.
Sorry,
Before i call the Algorithm I use Arrays.sort() on the Arrays.

#5

Found some code online with a quick google that works:

public int interpolationSearch(int[] array, int value, int from, int to){
	    if(array[from] == value) return from; 
	    else if(from == to || array[from] ==  array[to]) return -1; //not found

	    //probable position of the searched value
@@	    int index = from + ((to - from)/(array[to] - array[from])) * (value - array[from]);
	    
	    if(array[index] == value) return index;//found
	    //continue in the right part of the array
	    else if(array[index] < value) return interpolationSearch(array, value, index + 1, to);
	    //continue in the left part of the array
	    else return interpolationSearch(array, value, from, index - 1);
	}

The highlighted line is where your implementation broke.

#6

That´s strange…
It is the same code, why is it working in this order?..

But i´ts still not working correctly.
I am always getting an linear search…

#7

Okay, I gues i got it, but I have no clue how to solve it…

When you are dividing its very probable that your value is >0 and <1 so, an int will make an 0.
So I make every partcalculation extra and use double.

Edit:
So,… changed the stuff completly to double.
It seems that it´s work correctly.

But I still have the problem that I get too high numbers, if the numbers are higher than 10 signs.
So, I used BigInt and BigDecimal , but the funny thing is.
When I am using that it´s cutting the Values like an Integer. So, the 0.14 becomes an 0 and with that I get an wrong pivot…

#8

First multiply, then divide. No need for doubles.

#9

I edited my above post^^

Well, as I already wrote, it´s working but only for “little” numbers.
So I have to use BigDec. - which has an strange beaviour :open_mouth:
Now everything is in BigDecimal and it works.
I first had the feeling that it´s again an linear search, but it´s not.

When I am using an array with <15 it becomes nearly linear and when I am using ~100 values it needs approx <5 steps to find the searched value.

Thanks for your help!

#10

Why do you need BigDecimal? I’ll bet you don’t, plus it probably negates most any speed you would have gained over binarySearch.

#11

So, what code are you using now?

You only have to make this patch to make it lose less precision:


public int interpolationSearch(int[] array, int value, int from, int to){
       if(array[from] == value) return from; 
       else if(from == to || array[from] ==  array[to]) return -1; //not found

       //probable position of the searched value
-       int index = from + ((to - from)/(array[to] - array[from])) * (value - array[from]);
+       int index = from + ((to - from)*(value - array[from])) / (array[to] - array[from]);

       if(array[index] == value) return index;//found
       //continue in the right part of the array
       else if(array[index] < value) return interpolationSearch(array, value, index + 1, to);
       //continue in the left part of the array
       else return interpolationSearch(array, value, from, index - 1);
   }