Find the largest element smaller than X in a sorted array with non-decreasing consecutive differences, in O( log(log (max_value)))

Question

I want to find the largest element that is smaller than x in a sorted array, where the differences between the consecutive elements of the array are non-decreasing.

For example:

[1, 3, 10, 17, 50, 1000] is a valid input , because the consecutive differences (2,7,7,33,950) are in increasing order.

[1, 3, 4, 10, 18] is not a valid input, as the consecutive differences (2, 1, 6, 8) are not in increasing order.

The optimum solution is O(log(log max_value)), so I am looking for better solutions than upperbound/ binary search. Actually ,I am looking to optimize binary search from O(log N) to O(log(log max_value).

#include <bits/stdc++.h>

using namespace std;

const int n = 50000001;
int arr[n];

int binarysearch_lowerbound(int begin, int end, int x)
{
    int ans = end;
    while (begin < end) {
        int mid = (begin + end) / 2;
        if (arr[mid] >= x) {
            ans = mid;
            end = mid;
        }
        else {
            begin = mid + 1;
        }
    }
    return ans;
}
int main()
{
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;
        int k;
        int begin = x / (arr[N - 1] - arr[N - 2]);
        int end = x / (arr[1] - arr[0]);
        if (end > N - 1) {
            end = N;
        }
        k = binarysearch_lowerbound(begin, end, x);
        cout << arr[k - 1] << endl;
    }
    return 0;
}

Answer 1

To get O(log log N), you're probably going to need to use an interpolating search instead of a binary search.

In an interpolating search, you take the value you're looking for, and the minimum and maximum values in the array, and based on them you guess at a likely location for the element you're looking for, rather than blindly guessing the middle of the unknown portion of the array.

The simple case is when your elements are distributed approximately uniformly in the array, in which case you can use linear interpolation to guess at the point to search.

In your case, the data follows a distribution that's definitely non-linear, so you want to predict the location based on that, rather than linear interpolation. As a first approximation, let's assume it's roughly quadratic.

For a first test, let's start with a set of numbers that precisely follow a quadratic distribution: [1, 4, 9, 16, 25, 36, 49, 64]. We're going to search for the largest value less than 30. Our set has 8 values with a range of 1..64 = 63.

If we used linear interpolation, to search for 30, our initial guess would be 30/63*8 = 3 or 4 (which would actually be pretty accurate in this case).

To do a quadratic interpolation, we'd start by taking the square roots of the top and bottom of the range (8 and 1 respective), then taking the square root of 30 (~5.5) and doing linear in interpolation with those (5.5/(8-1) * 8) to get our initial guess.

From there, we continue much like we would in an binary search--if our number is larger than the value we found, we do a new interpolation among the larger numbers, and if it's smaller, we do a new interpolation among the smaller numbers.

The difficult part in all this is finding a function that actually fits your numbers reasonably well. In your case, that may be particularly problematic because you've been given only a tiny bit of information about the distribution. The requirement that the differences can't decrease means it's at least linear, but beyond that, we really don't know--it could be linear, or N^1.1, or N¹⁰, or possibly even something like N!. Linear interpolation won't fit a factorial distribution very well (nor vice versa).