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?