1.4.10

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

解答

修改二分查找的结束条件,找到后仍然向左侧寻找,如果还能找到更小的,则返回较小的下标;否则返回当前下标。

代码

namespace _1._4._10
{
    /// <summary>
    /// 二分查找。
    /// </summary>
    public class BinarySearch
    {
        /// <summary>
        /// 用递归方法进行二分查找。
        /// </summary>
        /// <param name="key">关键字。</param>
        /// <param name="a">查找范围。</param>
        /// <param name="lo">查找的起始下标。</param>
        /// <param name="hi">查找的结束下标。</param>
        /// <returns>返回下标,如果没有找到则返回 -1。</returns>
        public static int Rank(int key, int[] a, int lo, int hi)
        {
            if (hi < lo)
                return -1;
            int mid = (hi - lo) / 2 + lo;
            if (a[mid] == key)
            {
                int mini = Rank(key, a, lo, mid - 1);
                if (mini != -1)
                    return mini;
                return mid;
            }
            else if (a[mid] < key)
            {
                return Rank(key, a, mid + 1, hi);
            }
            else
            {
                return Rank(key, a, lo, mid - 1);
            }
        }
    }
}
上一题 下一题