top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

What is the difference between Interpolation search vs Binary search?

+2 votes
2,788 views
What is the difference between Interpolation search vs Binary search?
posted Apr 8, 2014 by Vishvachi Tiwari

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

2 Answers

0 votes

On average the interpolation search makes about log(log(n)) comparisons (if the elements are uniformly distributed), where n is the number of elements to be searched. In the worst case (for instance where the numerical values of the keys increase exponentially) it can make up to O(n) comparisons.More Info

answer Apr 8, 2014 by Atul Mishra
0 votes

Interpolation search (sometimes referred to as extrapolation search) is an algorithm for searching for a given key value in an indexed array that has been ordered by the values of the key.

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) which is better then binary search.

Sample Code

int interpolationSearch(int[] sortedArray, int toFind){
  // Returns index of toFind in sortedArray, or -1 if not found
  int low = 0;
  int high = sortedArray.length - 1;
  int mid;

  while (sortedArray[low] <= toFind && sortedArray[high] >= toFind) {
   mid = low +
         ((toFind - sortedArray[low]) * (high - low)) /
         (sortedArray[high] - sortedArray[low]);  //out of range is possible  here

   if (sortedArray[mid] < toFind)
    low = mid + 1;
   else if (sortedArray[mid] > toFind)
    // Repetition of the comparison code is forced by syntax limitations.
    high = mid - 1;
   else
    return mid;
  }

  if (sortedArray[low] == toFind)
   return low;
  else
   return -1; // Not found
 }

Credit: https://en.wikipedia.org/wiki/Interpolation_search

answer Apr 8, 2014 by Salil Agrawal
...