1.4.23

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

根据书中的提示,将二分查找中判断相等的条件改为两个数的差小于等于 $1/N^2$。

代码

// 将二分查找中的相等判定条件修改为差值小于 x,其中 x = 1/N^2。
/// <summary>
/// 二分查找。
/// </summary>
/// <param name="a">查找范围。</param>
/// <param name="key">关键字。</param>
/// <returns>结果的下标,没有结果时返回 -1。</returns>
static int BinarySearch(double[] a, double key)
{
    int lo = 0;
    int hi = a.Length - 1;
    double threshold = 1.0 / (a.Length * a.Length);

    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (Math.Abs(a[mid] - key) <= threshold)
        {
            return mid;
        }
        else if (a[mid] < key)
        {
            lo = mid + 1;
        }
        else
        {
            hi = mid - 1;
        }
    }
    return -1;
}
上一题 下一题