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