1.4.23

1.4.23 #

解答 #

根据书中的提示，将二分查找中判断相等的条件改为两个数的差小于等于 $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)
{
    var lo = 0;
    var hi = a.Length - 1;
    var threshold = 1.0 / (a.Length * a.Length);

    while (lo <= hi)
    {
        var mid = lo + (hi - lo) / 2;
        if (Math.Abs(a[mid] - key) <= threshold)
        {
            return mid;
        }

        if (a[mid] < key)
        {
            lo = mid + 1;
        }
        else
        {
            hi = mid - 1;
        }
    }

    return -1;