1.4.10

1.4.10 #

解答 #

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

代码 #

public static int Rank(int key, int[] a, int lo, int hi)
{
    if (hi < lo)
        return -1;
    var mid = (hi - lo) / 2 + lo;
    if (a[mid] == key)
    {
        var mini = Rank(key, a, lo, mid - 1);
        if (mini != -1)
            return mini;
        return mid;
    }

    if (a[mid] < key)
    {
        return Rank(key, a, mid + 1, hi);
    }
    return Rank(key, a, lo, mid - 1);
}