PostingListSearch { public static int interpolationSearch(int[] a, int fromIndex, int toIndex, int key) { int low = fromIndex; int lowVal = a[low]; if (key - lowVal < LINEAR_SEARCH_THRESHOLD_2) { return linearSearch(a, low, toIndex, key); } int high = toIndex - 1; int diff = high - low; if (diff <= BINARY_SEARCH_THRESHOLD) { return binarySearch(a, low, toIndex, key); } int highVal = a[high]; do { if (key == lowVal) { return low + 1; } if (key >= highVal) { return high + 1; } int mean = (int) (diff * (long) (key - lowVal) / (highVal - lowVal)); int eps = diff >>> 4; int lowMid = low + Math.max(0, mean - eps); int highMid = low + Math.min(diff, mean + eps); assert lowMid <= highMid; assert lowMid >= low; assert highMid <= high; if (a[lowMid] > key) { high = lowMid; highVal = a[lowMid]; } else if (a[highMid] <= key) { low = highMid; lowVal = a[highMid]; } else { low = lowMid; lowVal = a[lowMid]; high = highMid; highVal = a[highMid]; } assert low <= high; diff = high - low; } while (diff >= BINARY_SEARCH_THRESHOLD); return binarySearch(a, low, high + 1, key); }  static int interpolationSearch(int[] a, int fromIndex, int toIndex, int key); static final int LINEAR_SEARCH_THRESHOLD; static final int LINEAR_SEARCH_THRESHOLD_2; static final int BINARY_SEARCH_THRESHOLD; }
@Test public void require_that_search_find_index_of_first_element_higher() { int[] values = {2, 8, 4000, 4001, 4100, 10000, 10000000}; int length = values.length; assertEquals(0, PostingListSearch.interpolationSearch(values, 0, length, 1)); for (int value = 3; value < 8; value++) { assertEquals(1, PostingListSearch.interpolationSearch(values, 0, length, value)); } assertEquals(2, PostingListSearch.interpolationSearch(values, 0, length, 8)); assertEquals(values.length, PostingListSearch.interpolationSearch(values, 0, length, 10000000)); assertEquals(values.length, PostingListSearch.interpolationSearch(values, 0, length, 10000001)); }
@Test public void require_that_search_is_correct_for_one_size_arrays() { int[] values = {100}; assertEquals(0, PostingListSearch.interpolationSearch(values, 0, 1, 0)); assertEquals(0, PostingListSearch.interpolationSearch(values, 0, 1, 99)); assertEquals(1, PostingListSearch.interpolationSearch(values, 0, 1, 100)); assertEquals(1, PostingListSearch.interpolationSearch(values, 0, 1, 101)); assertEquals(1, PostingListSearch.interpolationSearch(values, 0, 1, 10000)); }
@Test public void require_that_search_is_correct_for_sub_arrays() { int[] values = {0, 2, 8, 4000, 4001, 4100}; assertEquals(1, PostingListSearch.interpolationSearch(values, 1, 2, 1)); assertEquals(2, PostingListSearch.interpolationSearch(values, 1, 2, 2)); assertEquals(2, PostingListSearch.interpolationSearch(values, 1, 4, 2)); assertEquals(4, PostingListSearch.interpolationSearch(values, 1, 4, 4000)); assertEquals(5, PostingListSearch.interpolationSearch(values, 1, 5, 4001)); assertEquals(5, PostingListSearch.interpolationSearch(values, 1, 5, 4101)); }
@Test public void require_that_search_is_correct_for_large_arrays() { int length = 10000; int[] values = new int[length]; for (int i = 0; i < length; i++) { values[i] = 2 * i; } assertEquals(1, PostingListSearch.interpolationSearch(values, 1, length, 0)); assertEquals(1227, PostingListSearch.interpolationSearch(values, 1, length, 2452)); assertEquals(1227, PostingListSearch.interpolationSearch(values, 1, length, 2453)); assertEquals(1228, PostingListSearch.interpolationSearch(values, 1, length, 2454)); }