I. Implement interpolationSearch method

An interpolation search assumes that the data in an array is sorted and uniformly distributed.

Whereas a binary search always looks at the middle item in an array, an interpolation search looks where the sought-for item is more likely to occur. For example, if you searched your telephone book for Victoria Appleseed, you probably would look near its beginning rather than its middle. And if you discovered many Appleseeds, you would look near the last Appleseed.

Hence the difference between the binary search and the interpolation search is that the binary search always splits the array in half and inspects the middle element, where the interpolation search calculates a probable position p, where the value should be found in accordance to the distribution of values, and splits the array at p. If the array contains numbers 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 and we are looking for 9 the binary search needs three steps split at 5, split at 8, split at 9 (found). The interpolation search calculates the probable position p (index 9) and immediately finds the value. The expected complexity of the interpolation search in O(log(log n)).

Instead of looking at the element a[mid] of an array a, as the binary search would, an interpolation search examines a[p], where p is calculated as follow:

int p = left + ((desiredItem - a[left]) * (right - left)/(a[right] - a[left]));

Implement the interpolation search for an array using recursion in InterpolationSearch.java class.

public class InterpolationSearch { /**  * Searches a portion of a sorted array of integers for a given value.  *  * @param a an array of integers sorted into ascending order  * @param left the integer index of the first array element;  * left >= 0 and < a.length  * @param right the integer index of the last array element;  * right - left >= 1; right < a.length  * @param desiredItem the item sought  * @return the index of desiredItem, or -1 if not found  */  public static int interpolationSearch(int[] a, int left, int right, int desiredItem) { // TODO Project 3  final int NOT_FOUND = -1; System.out.println("IMPLEMENT interpolationSearch recursively: desiredItem = " + desiredItem + "; left = " + left + "; right = " + right); // if desiredItem is at position left we found desiredItem // if position left is the same as position right // or element at position left is the same as the element at position right - desiredItem is not found // if left and right are out of logical order - desiredItem is not found // if desiredItem is smaller than the first element in the sub-array or larger than the last element in the sub-array // desiredItem is not found // otherwise compute p and search in a similar way as binary search would after computing mid // System.out.println("--> p = " + p); return NOT_FOUND; } // end interpolationSearch // some simple test cases of interpolation seach public static void main(String[] args) { int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22}; System.out.print("Searching uniformly distributed sorted array: "); for (int element : a) System.out.print(element + " "); System.out.println(); System.out.println(); int foundIndex = InterpolationSearch.interpolationSearch(a, 0, a.length - 1, 14); if (foundIndex == 13) System.out.println("PASSES: 14 was found at index 13"); else System.out.println("FAILS: 14 was not found at index 13; interpolationSearch returned " + foundIndex); foundIndex = InterpolationSearch.interpolationSearch(a, 0, a.length - 1, 1); if (foundIndex == 0) System.out.println("PASSES: 1 was found at index 0"); else System.out.println("FAILS: 1 was not found at index 0; interpolationSearch returned " + foundIndex); foundIndex = InterpolationSearch.interpolationSearch(a, 0, a.length - 1, 22); if (foundIndex == 21) System.out.println("PASSES: 22 was found at index 21"); else System.out.println("FAILS: 22 was not found at index 21; interpolationSearch returned " + foundIndex); foundIndex = InterpolationSearch.interpolationSearch(a, 0, a.length - 1, 20); if (foundIndex == 19) System.out.println("PASSES: 20 was found at index 19"); else System.out.println("FAILS: 20 was not found at index 19; interpolationSearch returned " + foundIndex); foundIndex = InterpolationSearch.interpolationSearch(a, 0, a.length - 1, 23456); if (foundIndex == -1) System.out.println("PASSES: 23456 was not found"); else System.out.println("FAILS: 23456 was found; interpolationSearch returned " + foundIndex); foundIndex = InterpolationSearch.interpolationSearch(a, 0, a.length - 1, -6); if (foundIndex == -1) System.out.println("PASSES: -6 was not found"); else System.out.println("FAILS: -6 was found; interpolationSearch returned " + foundIndex); foundIndex = InterpolationSearch.interpolationSearch(a, 0, a.length - 1, 12); if (foundIndex == 11) System.out.println("PASSES: 12 was found at index 11"); else System.out.println("FAILS: 12 was not found at index 11; interpolationSearch returned " + foundIndex); int b[] = {-10, -5, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 200, 700, 12345}; System.out.print(" Searching non-uniformly distributed sorted array: "); for (int element : b) System.out.print(element + " "); System.out.println(); System.out.println(); foundIndex = InterpolationSearch.interpolationSearch(b, 0, b.length - 1, 14); if (foundIndex == 13) System.out.println("PASSES: 14 was found at index 13"); else System.out.println("FAILS: 14 was not found at index 13; interpolationSearch returned " + foundIndex); foundIndex = InterpolationSearch.interpolationSearch(b, 0, b.length - 1, -10); if (foundIndex == 0) System.out.println("PASSES: -10 was found at index 0"); else System.out.println("FAILS: -10 was not found at index 0; interpolationSearch returned " + foundIndex); foundIndex = InterpolationSearch.interpolationSearch(b, 0, b.length - 1, 12345); if (foundIndex == 21) System.out.println("PASSES: 12345 was found at index 21"); else System.out.println("FAILS: 12345 was not found at index 21; interpolationSearch returned " + foundIndex); foundIndex = InterpolationSearch.interpolationSearch(b, 0, b.length - 1, 200); if (foundIndex == 19) System.out.println("PASSES: 200 was found at index 19"); else System.out.println("FAILS: 200 was not found at index 19; interpolationSearch returned " + foundIndex); foundIndex = InterpolationSearch.interpolationSearch(b, 0, b.length - 1, 23456); if (foundIndex == -1) System.out.println("PASSES: 23456 was not found"); else System.out.println("FAILS: 23456 was found; interpolationSearch returned " + foundIndex); foundIndex = InterpolationSearch.interpolationSearch(b, 0, b.length - 1, -6); if (foundIndex == -1) System.out.println("PASSES: -6 was not found"); else System.out.println("FAILS: -6 was found; interpolationSearch returned " + foundIndex); foundIndex = InterpolationSearch.interpolationSearch(b, 0, b.length - 1, 12); if (foundIndex == 11) System.out.println("PASSES: 12 was found at index 11"); else System.out.println("FAILS: 12 was not found at index 11; interpolationSearch returned " + foundIndex); System.out.println(" *** Done ***"); } // end main } // end Search

See sample run :

Searching uniformly distributed sorted array: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

--> p = 13

PASSES: 14 was found at index 13

PASSES: 1 was found at index 0

--> p = 21

PASSES: 22 was found at index 21

--> p = 19

PASSES: 20 was found at index 19

PASSES: 23456 was not found

PASSES: -6 was not found

--> p = 11

PASSES: 12 was found at index 11

Searching non-uniformly distributed sorted array: -10 -5 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 200 700 12345

--> p = 0

--> p = 1

--> p = 2

--> p = 3

--> p = 4

--> p = 5

--> p = 6

--> p = 7

--> p = 8

--> p = 9

--> p = 10

--> p = 11

--> p = 12

PASSES: 14 was found at index 13

PASSES: -10 was found at index 0

--> p = 21

PASSES: 12345 was found at index 21

--> p = 0

--> p = 1

--> p = 2

--> p = 3

--> p = 4

--> p = 5

--> p = 6

--> p = 7

--> p = 8

--> p = 9

--> p = 10

--> p = 11

--> p = 12

--> p = 13

--> p = 14

--> p = 15

--> p = 16

--> p = 17

--> p = 18

PASSES: 200 was found at index 19

PASSES: 23456 was not found

--> p = 0

PASSES: -6 was not found

--> p = 0

--> p = 1

--> p = 2

--> p = 3

--> p = 4

--> p = 5

--> p = 6

--> p = 7

--> p = 8

--> p = 9

--> p = 10

PASSES: 12 was found at index 11

*** Done ***