1.4.21

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

解答

直接将 Contains() 实现为二分查找即可。

代码

/// <summary>
/// 检查数组中是否存在指定元素。
/// </summary>
/// <param name="key">要查找的值。</param>
/// <returns>存在则返回 true,否则返回 false。</returns>
public bool Contains(int key)
{
    return Rank(key, 0, this.a.Length - 1) != -1;
}

/// <summary>
/// 二分查找。
/// </summary>
/// <param name="key">关键值。</param>
/// <param name="lo">查找的起始下标。</param>
/// <param name="hi">查找的结束下标。</param>
/// <returns>返回关键值的下标,如果不存在则返回 -1。</returns>
public int Rank(int key, int lo, int hi)
{
    while (lo <= hi)
    {
        int mid = (hi - lo) / 2 + lo;
        if (key < this.a[mid])
            hi = mid - 1;
        else if (key > this.a[mid])
            lo = mid + 1;
        else
            return mid;
    }
    return -1;
}
上一题 下一题