基于非线距离度量的连续区间二分搜索：术语与无界版本问询

我正在研究连续区间上采用非线性距离度量D的二分搜索问题。该区间搜索仅允许二元查询——只能获取当前x是否小于目标值x*的信息。核心目标是找到x*的ε近似解x'，满足D(x', x*) ≤ ε，同时我正尝试确立该问题的查询复杂度上下界。

这里的距离度量D是可计算区间内任意两点距离/差异的函数，满足D(·,·) → R₀⁺ ∪ ∞。有相关算法涉及连续搜索与ε近似输出，比如以下平方根求解算法：

my_sqrt(x):
    epsilon = 0.001 
    L = 0, R = x
    while (R - L > epsilon):
        mid = L + (R - L)/2
        if (mid*mid <= x):
            L = mid
        else:
            R = mid
    return L + (R - L)/2

该算法以线性函数（绝对值）作为距离度量，但我的研究重点是纳入非线性度量，例如对数比的平方根：对于区间内任意两点x和x'，距离计算公式为D(x, x') = sqrt(log(x) - log(x')) = sqrt(log(x/x'))。

我考虑将该问题命名为度量二分搜索（metric binary search），但有两个疑问：

• 是否存在相关的现有研究或通用术语？
• 是否有针对该算法无界版本的研究（类似二分搜索拓展至无界二分搜索的方向）？

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