如何在含已知delta函数的非均匀轴上快速定位数值位置

Great question! When dealing with non-uniformly spaced intervals where the delta (interval length) changes linearly, you have two main paths to fast lookup: analytical calculation (O(1) time if you can derive the formula) or binary search (O(logN) time, simple to implement even if you don't want to dive into math). Let's break this down based on how your linear_delta function is structured.

First, Clarify the Linear Delta Model #

You mentioned linear_delta is a linear function along the x-axis. There are two common interpretations here—let's cover both:

Case 1: Interval length is linear with respect to x position #

Suppose linear_delta(x) = m*x + b (where m is the slope, b is the intercept). Each interval's length depends on the starting x-value of that interval. The sequence of interval endpoints follows a linear recurrence relation:
x_{i+1} = x_i + linear_delta(x_i) = x_i*(1+m) + b

We can derive a closed-form formula for x_i (the i-th endpoint):

• If m ≠ 0 (non-uniform):
  x_i = (s + b/m) * (1+m)^i - b/m
• If m = 0 (uniform spacing):
  x_i = s + i*b

To find which interval a given x falls into:

1. Rearrange the formula to solve for i (take logarithms for the non-uniform case)
2. Take the integer part of the resulting value (floor it)
3. Verify the adjacent endpoints to confirm (to account for floating-point precision)

Case 2: Interval length is linear with respect to interval index #

Alternatively, maybe each interval's length increases/decreases linearly with its index: Δx_i = Δx₀ + i*k (where Δx₀ is the first interval's length, k is the step change per interval). The i-th endpoint is the sum of all previous interval lengths plus the start s:
x_i = s + i*Δx₀ + k*(i-1)*i/2

This is a quadratic function in i. To find the interval for x:

1. Set up the quadratic equation s + i*Δx₀ + k*(i-1)*i/2 = x
2. Solve for i using the quadratic formula
3. Take the floor of the positive solution, then verify the interval

The Universal Fast Solution: Binary Search #

If deriving the analytical formula feels too tedious, or if you're working with a large number of intervals (where storing all endpoints would use too much memory), binary search is your go-to. It's efficient (O(logN) time) and straightforward to implement.

Option 1: Precompute endpoints and use built-in bisect #

If memory isn't an issue, precompute all interval endpoints into an array, then use a bisect function to find the position:

import bisect

# Example: Precompute your endpoint array (replace with your actual generation logic)
s = 26.0
e = 50.21067768889078
x_arr = [s]
current_x = s
# Assume linear_delta is Δx_i = 0.1 + 0.02*i (example linear index-based delta)
i = 0
while current_x < e:
    delta = 0.1 + 0.02 * i
    next_x = current_x + delta
    # Ensure we don't exceed the end point
    next_x = min(next_x, e)
    x_arr.append(next_x)
    current_x = next_x
    i += 1

# Look up a given x
x = 35.0
idx = bisect.bisect_left(x_arr, x)
if idx == 0:
    print("Error: x is below the start of the x-axis")
elif idx == len(x_arr):
    print("Error: x is above the end of the x-axis")
else:
    print(f"x = {x} belongs to interval {idx-1}: [{x_arr[idx-1]:.6f}, {x_arr[idx]:.6f})")

Option 2: Binary search without storing all endpoints #

For very large N, avoid storing the entire array by calculating endpoints on the fly during the binary search:

def find_interval(x, s, e):
    # First, handle boundary cases
    if x < s:
        return -1  # Below start
    if x >= e:
        return None  # Above end
    
    # Estimate upper bound for interval index
    # Start with a rough guess and double until we exceed x
    high = 1
    while calculate_endpoint(high, s) <= x:
        high *= 2
    
    low = 0
    # Binary search to find the largest i where endpoint(i) <= x
    while low < high:
        mid = (low + high + 1) // 2  # Use ceiling to avoid infinite loop
        mid_x = calculate_endpoint(mid, s)
        if mid_x <= x:
            low = mid
        else:
            high = mid - 1
    return low

def calculate_endpoint(i, s):
    # Implement this based on your linear_delta model
    # Example for index-based linear delta: Δx_i = 0.1 + 0.02*i
    current_x = s
    for idx in range(i):
        delta = 0.1 + 0.02 * idx
        current_x += delta
    # Ensure we don't exceed e (optional, depending on your setup)
    return min(current_x, 50.21067768889078)

# Usage
s = 26.0
e = 50.21067768889078
x = 35.0
interval_idx = find_interval(x, s, e)
if interval_idx == -1:
    print("x is below the start")
elif interval_idx is None:
    print("x is above the end")
else:
    print(f"x belongs to interval {interval_idx}")

Key Takeaways #

• Analytical calculation gives you O(1) lookup time if you can derive the endpoint formula—ideal for performance-critical code.
• Binary search is simpler to implement, works for any monotonic non-uniform spacing, and is still extremely fast even for large N.
• Always handle edge cases where x is outside the [s, e] range.

内容的提问来源于stack exchange，提问作者Dnaiel