Beating the binary search algorithm - interpolation search, galloping search

Beating the binary search algorithm – interpolation search, galloping search
Binary search
Because of the random jumps of the binary search, this algorithm is not cache friendly so some fine tuned versions would switch back to linear search as long as the size of the search space is less than a specified value (64 or less typically).
Galloping search; galloping search with binary search fallback

If the length of the array is unknown for some reason, the galloping search can identify the initial range of the search scope. This algorithm starts at the first element and keeps doubling the upper limit of the search range until the value there is larger than the searched key. After this, depending on the implementation, the search either falls back to a standard binary search on the selected range, or restarts another galloping search. The former one guarantees an O(log(n)) runtime, the latter one is closer to O(n) runtime.
Galloping search is efficient if we expect to find the element closer to the beginning of the array.
Interpolation search; interpolation search with sequential fallback
As a first step it samples the beginning and the end of the search space and then guesses the element’s location. It keeps repeating this step until the element is found. If the guesses are accurate, the number of comparisons can be around O(log(log(n)), runtime aroundO(log(n)), but unlucky guesses easily push it up to O(n).
Interpolation search:    public int search(final int[] arr, final int val, int left, int right) {
        if (arr == null || arr.length == 0 || arr[left] > val || arr[right - 1] < val) {
            return -1;
        }
        while (left < right && left >= 0 && right <= arr.length) { //maybe not needed?  left>=0&&right<=len
            final int leftValue = arr[left];
            final int rightValue = arr[right - 1];
            final float average = ((float) rightValue - leftValue) / (right - left);
            int midpoint = left;
            if (average != 0) {
                final int diff = val - leftValue;
                final int steps = (int) (diff / average);
                midpoint = left + steps;
                // Overshoots.
                if (midpoint >= right) {
                    midpoint = (left + right) / 2;
                }
            }
            final int mid = arr[midpoint];
            if (mid == val) {
                return midpoint;
            }
            final int err = val - mid;
            if (Math.abs(err) < distance * average) {
                return sequential(arr, val, midpoint, err);
            }
            if (val < mid) {
                right = midpoint - 1;
            } else {
                left = midpoint + 1;
            }
        }
        // because we are using left<(no =) right
        if (arr[left] == val) {
            return left;
        }
        return -1;
    }
GallopBinary
    public int search(final int[] arr, final int val, int left, int right) {
        if (arr == null || arr.length == 0 || arr[left] > val || arr[right - 1] < val) {
            return -1;
        }
        int jump = 1;
        while (left <= right) {
            final int curr = arr[left];
            if (curr == val) {
                return left;
            }
            final int next = left + jump;
            if (curr > val || next > right) {
                if (curr > val) {
                    right = left;
                }
                left -= jump / 2;
                left++;
                return binary.search(arr, val, left, right);
            }
            left = next;
            jump *= 2;
        }

        return -1;
    }
Binary Search:
public int search(final int[] arr, final int val, int left, int right) {
    // argument check, and exit early
    if (arr == null || arr.length == 0 || arr[left] > val || arr[right - 1] < val) {
        return -1;
    }
    while (left <= right) { // detail <= when left=right, then midpoint=left=right, it will do the check
        final int midpoint = (left + right) / 2;
        final int mid = arr[midpoint];
        if (val < mid) {
            right = midpoint - 1; //mid-1
        } else if (mid == val) {
            return midpoint;
        } else {
            left = midpoint + 1; // mid+1
        }
    }
    return -1; //
}

Read full article from Beating the binary search algorithm – interpolation search, galloping search