Write an Interpolation Search method Interpolation search is similar to binary s

Question

Write an Interpolation Search method Interpolation search is similar to binary search, except it tries to begin the search nearer to the location of the item. Instead of the using the middle value of the sorted array, interpolation search estimates the location of the target with respect to the first & last values in the array. The implementation is the same as binary search except that you should calculate the mid value as: mid first+ ((last first) (searchKey - arr[first])) , (arr[last] -arr[first]) * - Note that Interpolation Search will only work with numeric types! You only need to be concerned with sorting an array of integers. Write code to test your search.

Explanation / Answer

Hi friend, You have not mentioned about programming language.

Please find my implementation in JAva.

public class InterpolationSearch

{

// If x is present in arr[0..n-1], then returns

// index of it, else returns -1.

static int interpolationSearch(int[]arr, int x)

{

// Find indexes of two corners

int lo = 0, hi = (arr.length - 1);

  

// Since array is sorted, an element present

// in array must be in range defined by corner

while (lo <= hi && x >= arr[lo] && x <= arr[hi])

{

// Probing the position with keeping

// uniform distribution in mind.

int pos = lo + (((hi-lo) /

(arr[hi]-arr[lo]))*(x - arr[lo]));

  

// Condition of target found

if (arr[pos] == x)

return pos;

  

// If x is larger, x is in upper part

if (arr[pos] < x)

lo = pos + 1;

  

// If x is smaller, x is in lower part

else

hi = pos - 1;

}

return -1;

}

// Driver method

public static void main(String[] args)

{

int arr[] = new int[]{10, 12, 13, 16, 18, 19, 20, 21, 22, 23,

   24, 33, 35, 42, 47};

   int x = 18; // Element to be searched

   int index = interpolationSearch(arr, x);

  

   // If element was found

   if (index != -1)

System.out.println("Element found at index " + index);

   else

System.out.println("Element not found.");

}

}

/*

Sample run:

Element found at index 4

*/

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.