Efficient implementation of finding segment number falls into

Let us divide the numbers between 0 and n, for potentially large n into s segments: 0 = n_0 < n_1 < ... < n_s = n. Given a number 0 <= x < n, we can find s such that n_(s - 1) < x <= n_s in O(s) space and O(log(s)) time by binary search, or O(n) space and O(1) time by a lookup table. Is it possible to do better? Trade off space for time complexity?

You can make your average performance faster at the price of making your worst case slower.

To demonstrate, let's consider the case where s is fairly large, but is much smaller than n. How many things in s are before a proportion p of the way through n? We can model this as picking s-2 random numbers in the range from 1 to n-1. Each has an almost independent (thanks to the assumption that s is much smaller than n) probability p of being less than n*p. Standard probability says that each is a random variable with mean p and variance p * (1-p). Their sum is approximately normal with mean avg = p*(s-2) and variance p * (1-p) * (s-2). The standard deviation std is sqrt(p * (1-p) * (s-2)). About 95% of the time we will be within 2 standard deviations of the average. (If you prefer, about 99.7% we will be within 3 standard deviations.)

Therefore looking at the values of the sequence at avg + 2*std and avg - 2*std, about 95% of the time we can reduce the range to search to within 2*std = O(sqrt(s)). Doing so O(log(log(s))) times will reduce the answer to 1. (If you prefer, use a 3 instead of 2, and the bounds are wider, but the odds are 99.7%.)

It is actually better to not produce 2 guesses at a time. Just figure out the average, and then go 2 (or 3 if you prefer) standard deviations towards the half-way point (stopping there if you would pass it). After seeing the answer you can then make the other guess much more precisely. The average runtime remains the same.

Now this goes at the cost of making the worst case performance much worse. But if you simply choose the halfway point one time in 10, you can keep the worst case O(log(s)) (with worse constants) while still enjoying the improved O(log(log(s))) better average time.

Here is a quick demonstration without the standard deviation logic. I left a debugging step so that you can see how many guesses it makes.

def find(s, x):
    low_i = -1
    high_i = len(s)
    low_val = s[low_i+1]
    high_val = s[high_i-1]
    counter = 0
    while low_i + 1 < high_i:
        if 50 < counter:
            break
        counter += 1
        if 0 == counter%8:
            # Guarantee progress
            mid_i = (high_i + low_i)//2
        else:
            p = (x - low_val) / (high_val - low_val)
            mid_i = round(low_i + p * (high_i - low_i))

        # Must be in our range.
        if mid_i == low_i:
            mid_i += 1
        elif mid_i == high_i:
            mid_i -= 1

        print(counter, (low_i, high_i), (low_val, high_val), mid_i, s[mid_i])
        if s[mid_i] < x:
            low_i = mid_i
            low_val = s[low_i]
        else:
            high_i = mid_i
            high_val = s[high_i]
    return (mid_i, s[mid_i])

And then to give it a realistic test.

import random
n = 10**12
numbers = set([0, n])
while len(numbers) < 10**6:
    numbers.add(random.randint(0, n))

numbers = sorted(numbers)
find(numbers, random.randint(0, n))

We have a million numbers from 0 through a trillion. Finding the correct range from binary guessing should take 20 guesses. This usually takes 4-6 guesses instead.