高效精确浮点二分查找：简化between函数实现方案问询

以下是一段用于查找**大于lo且小于等于hi**值的二分查找代码：

find(lo: number, hi: number, isTooLow: (testVal: number) => boolean) {
    for(;;) {
        const testVal = between(lo, hi);
        if (testVal <= lo || testVal >= hi) {
            break;
        }
        if (isTooLow(testVal)) {
            lo = testVal;
        } else {
            hi = testVal;
        }
    }
    return hi;
}

这里的number是64位浮点数。这段搜索逻辑必然会终止，如果把between函数实现为选取lo和hi之间的64位浮点数中位数（如果存在），可以达成两个目标：

• 64次迭代内终止
• 精准找到使isTooLow(hi) == false的最小hi值

但这类between函数的实现非常复杂，需要依赖浮点数的具体表示细节。

现在我们需要一个更简单的between函数实现，只依赖浮点数的通用特性（固定宽度尾数、固定宽度指数和符号位），不需要了解具体表示细节，用JavaScript实现，满足以下要求：

• 约200次迭代内终止
• 找到的hi值与目标最小hi值相差3-4个可能值
• 优先避免使用超越函数和平方根函数

最终解决方案 #

采用先指数搜索缩小范围，再进行常规二分查找的思路，实现代码如下：

function find(lo: number, hi: number, isTooLow: (testVal: number) => boolean) {
    [lo, hi] = getLinearRange(lo, hi, isTooLow);
    for (; ;) {
        const testVal = lo + (hi - lo) * 0.5;
        if (testVal <= lo || testVal >= hi) {
            break;
        }
        if (isTooLow(testVal)) {
            lo = testVal;
        } else {
            hi = testVal;
        }
    }
    return hi;
}

/**
 * 将浮点数范围缩小到适合常规二分查找的大小
 * @returns [newlow, newhigh]
 */
function getLinearRange(
    low: number, high: number,
    isTooLow: (n: number) => boolean): [number, number] {

    let negRange: [number, number] | undefined;
    if (low < 0) {
        if (high > 0) {
            if (isTooLow(0)) {
                return scaleRange(0, high, 0.25, isTooLow);
            } else {
                const isTooHigh = (n: number) => !isTooLow(n);
                negRange = scaleRange(0, -low, 0.25, isTooHigh);
            }
        } else {
            const isTooHigh = (n: number) => !isTooLow(n);
            negRange = scaleRange(-high, -low, 0.25, isTooHigh);
        }
    } else {
        return scaleRange(low, high, 0.25, isTooLow);
    }
    // 对范围取反
    low = -negRange[1];
    negRange[1] = -negRange[0];
    negRange[0] = low;
    return negRange;
}

/**
 * 缩小正数范围，直到 low/high >= minScale
 * @returns [newlow, newhigh]
 */
function scaleRange(
    low: number, high: number, minScale: number,
    isTooLow: (n: number) => boolean): [number, number] {

    if (!(minScale > 0 && low < high * minScale)) {
        return [low, high];
    }
    const range = scaleRange(low, high, minScale * minScale, isTooLow);
    [low, high] = range;
    const test = high * minScale;
    if (test > low && test < high) {
        if (isTooLow(test)) {
            range[0] = test;
        } else {
            range[1] = test;
        }
    }
    return range;
}

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