# Binary Interpolation Search ... but why?

Page 1 of 1

## 11 Replies - 1218 Views - Last Post: 01 May 2017 - 04:46 PM

### #1 general656

• D.I.C Regular

Reputation: 12
• Posts: 288
• Joined: 25-March 15

# Binary Interpolation Search ... but why?

Posted 29 April 2017 - 07:32 AM

I tested out Binary Interpolation Search and compared the results to Binary Search.
The results ... were dramatic. :tun tun tun:

For a size of 1 BILLION :dollars:

I tested the two algorithms. I can tell that Binary Interpolation Search had even worse results than linear for some damn reason. Here are the codes just for the record:

Linear Search:

```int linearSearch (int *list, int l, int r, int key) {
int found = 0, i = l;
while (!found && i < r) {
if (list[i] == key) return i;
++i;
}
return -1;
}
```

Binary Search:

```int binarySearch(int *list, int l, int r, int key) {
if (r >= l)
{
int mid = l + (r - l)/2;

// If the element is present at the middle itself
if (list[mid] == key)  return mid;

// If element is smaller than mid, then it can only be present
// in left subarray
if (list[mid] > key) return binarySearch(list, l, mid-1, key);

// Else the element can only be present in right subarray
return binarySearch(list, mid+1, r, key);
}

// We reach here when element is not present in array
return -1;
}
```

Binary Interpolation Search:
(which code or even name I couldn't find ANYWHERE on google, its like no one uses this algorithm)

```int bisSearch (int *arr, int l, int r, int key)  {
int left 	= l;
int right 	= r;

int size = right - left;
int next = (int) (size * ((key - arr[left])/(arr[right] - arr[left]))) + 1;

while (key != arr[next]) {
int i = 0;
size = right - left;
if (size <= 3)
return linearSearch (arr, l, r, key);
if (key >= arr[next]) {
while (key > arr[next + i*((int) sqrt(size)) - 1]) {
++i;
}
right = next + (int) (i*sqrt(size));
left  = next + (int) ((i-1)*sqrt(size));
}
else if (key < arr[next]) {
while (key < arr[next -i* ((int) sqrt(size)) + 1]) {
++i;
}
right = next - (int) ((i-1)*sqrt(size));
left  = next - (int) (i*sqrt(size));
}
next = (int) (left + ((right - left +1)*(key - arr[left])/(arr[right] - arr[left]))) - 1;

}
if (key = arr[next])
return next;
else return -1;
}
```

Last time, I tested it out with INT_MAX.
Binary Interpolation did around 2sec to find the given key, Linear Searching around 0.08sec but oh Binary Search ... did 0.000003secs.

So... what the heck? Why this "Interpolation" with the "loglogN" bigO has so bad timings every time I run it?

I run it with random numbers in the list (which were sorted) it got horrible results. I run it with close together numbers (like you can see in the main below, as the number is the same with its index), again horrible results.

Where is the "loglogN"? Why does BinarySearch with "logN" minumum runs so much significantly better than Binary InterpolationSearch?

PS.
My main just for the record ... :
```#define SUPERBIGLENGTH INT_MAX
int main () {
srand(time(NULL));
clock_t begin, end;

int *arr = (int*) malloc (SUPERBIGLENGTH * sizeof(int));
for (int i = 0; i < SUPERBIGLENGTH; i++) {
arr[i] = i;
}

double avgtime = 0;
for (int i=0; i<10; i++) {
int ind = rand() % SUPERBIGLENGTH;
int key = arr[SUPERBIGLENGTH/1000];

begin = clock();
int index = linearSearch (arr, 0, SUPERBIGLENGTH-1, key);
end   = clock();

double totalTime = (double) (end - begin) / CLOCKS_PER_SEC;
printf ("\$%fs\n", totalTime);
avgtime += totalTime;
}
avgtime /= 10;

printf("TOTAL TIIIIIIIME: %fs\n", avgtime);

return 0;
}
```

This post has been edited by general656: 29 April 2017 - 07:40 AM

Is This A Good Question/Topic? 0

## Replies To: Binary Interpolation Search ... but why?

### #2 modi123_1

• Suitor #2

Reputation: 14089
• Posts: 56,444
• Joined: 12-June 08

## Re: Binary Interpolation Search ... but why?

Posted 29 April 2017 - 09:42 AM

Do you just mean 'Interpolation search'?

### #3 Skydiver

• Code herder

Reputation: 6216
• Posts: 21,452
• Joined: 05-May 12

## Re: Binary Interpolation Search ... but why?

Posted 29 April 2017 - 10:49 AM

Are you timing the byld with full optimizations? Did you make sure to commute sqrt(size) only once each time size changes?

### #4 Skydiver

• Code herder

Reputation: 6216
• Posts: 21,452
• Joined: 05-May 12

## Re: Binary Interpolation Search ... but why?

Posted 29 April 2017 - 12:45 PM

Also consider that after sqrt(), division and multiplication operations are also expensive.

### #5 general656

• D.I.C Regular

Reputation: 12
• Posts: 288
• Joined: 25-March 15

## Re: Binary Interpolation Search ... but why?

Posted 29 April 2017 - 12:52 PM

modi123_1, on 29 April 2017 - 09:42 AM, said:

Do you just mean 'Interpolation search'?

No, but I'm not surprised that you didn't know it. Oh my god. It's like no one knows this algorithm. I've searched on Google everywhere and no implementation was found. But some people know about it.

Since recently, I didn't even know "Interpolation Search", not only Binary Interpolation Search.
Our professor taught us about it.

Binary Interpolation Search is a combination of Interpolation Search With Binary Searching technique.
Basically ... what it is is a "Dynamic Interpolation Search" with a dynamic "mid" variable, that instead of doing a fixed step, it adjusts statistically.

But I don't see the point. Obviously, since no one knows it, no one uses it as well and as much as I saw the damn timings are shitty. It's not good to use.

Skydiver, on 29 April 2017 - 10:49 AM, said:

Are you timing the byld with full optimizations? Did you make sure to commute sqrt(size) only once each time size changes?

Heyyyyyy ... I can't understand what you're saying
But all the code is above anyways you can answer it yourself Thank you by the way

### #6 modi123_1

• Suitor #2

Reputation: 14089
• Posts: 56,444
• Joined: 12-June 08

## Re: Binary Interpolation Search ... but why?

Posted 29 April 2017 - 01:08 PM

Quote

Oh my god. It's like no one knows this algorithm.

Obscure, unused, or oddly named algorithms are indeed obscure, unused, and odd.

### #7 Skydiver

• Code herder

Reputation: 6216
• Posts: 21,452
• Joined: 05-May 12

## Re: Binary Interpolation Search ... but why?

Posted 29 April 2017 - 01:11 PM

Sorry. Trying to type on a phone. When you compiled (e.g built) your code, did you compile with -O3 if gcc is your compiler, or -Ox if MSVC is your compiler?

Did you manually optimize the code to compute sqrt(size) only once near the beginning of the other while loop?

When I get home I will likely try some profiling runs against fully optimized builds.

### #8 Skydiver

• Code herder

Reputation: 6216
• Posts: 21,452
• Joined: 05-May 12

## Re: Binary Interpolation Search ... but why?

Posted 29 April 2017 - 01:42 PM

general656, on 29 April 2017 - 10:32 AM, said:

Where is the "loglogN"? Why does BinarySearch with "logN" minumum runs so much significantly better than Binary InterpolationSearch?

Apparently, you need a special data structure according to Wikipedia. A vanilla array ain't gonna cut it:

Quote

Using big-O notation, the performance of the interpolation algorithm on a data set of size n is O(n); however under the assumption of a uniform distribution of the data on the linear scale used for interpolation, the performance can be shown to be O(log log n). However, Dynamic Interpolation Search is possible in o(log log n) time using a novel data structure.

### #9 Skydiver

• Code herder

Reputation: 6216
• Posts: 21,452
• Joined: 05-May 12

## Re: Binary Interpolation Search ... but why?

Posted 29 April 2017 - 03:11 PM

Interestingly, that same quote predicts O(log log n) for evenly distributed keys, which is the case for your data set for that main(), that you showed above.

Looking at that code for biSearch(), the bug looks to be that you are doing integer division instead of floating point division on line 6. Due to that bug, you are essentially doing a linear probe from the beginning of the search segment until you find a segment that may contain the target value, and then you do the same operation with that new segment.

As an aside, if you change the tail recursion of your normal binary search to iteration the same way your binary interpolation search does iterations, the normal binary search will be even faster.

### #10 Skydiver

• Code herder

Reputation: 6216
• Posts: 21,452
• Joined: 05-May 12

## Re: Binary Interpolation Search ... but why?

Posted 01 May 2017 - 07:23 AM

I still haven't gotten around to doing some profiling runs, but looking around on line for various implementations of "binary interpolation search", I don't see the characteristic of your implementation where it does multiple probes trying to find a sqrt(size) sized segment that the value maybe in. All the implementations I've seen simply interpolate an index based on the value, check for a match, and if not, go use either the low half or high half as a result of the interpolation. Additionally, I haven't seen the switch over to using linear search at the point when the segment size goes below a particular threshold (except for various things talking about how to optimize searching).

### #11 general656

• D.I.C Regular

Reputation: 12
• Posts: 288
• Joined: 25-March 15

## Re: Binary Interpolation Search ... but why?

Posted 01 May 2017 - 11:52 AM

Skydiver, on 01 May 2017 - 07:23 AM, said:

All the implementations I've seen [..]

Wait, you found a site with an implementation of Binary Interpolation Search?

### #12 Skydiver

• Code herder

Reputation: 6216
• Posts: 21,452
• Joined: 05-May 12

## Re: Binary Interpolation Search ... but why?

Posted 01 May 2017 - 04:46 PM