@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)); }
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); }
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); } }
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); }  }
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); }
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; }