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

*to find the given key, Linear Searching around*

**2sec****but oh Binary Search ... did**

*0.08sec**.*

**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