1.4.18

1.4.18 #

解答 #

和二分查找的方式类似，先确认中间的值是否是局部最小，如果不是，则向较小的一侧二分查找。

在三个数中比较得到最小值需要两次比较，因此最坏情况下为 $~2\lg N$ 次比较。

代码 #

var a = new[] { 1, 2, 5, 3, 5 };
Console.WriteLine(LocalMinimum(a));

static int LocalMinimum(int[] a)
{
    var lo = 0;
    var hi = a.Length - 1;
    while (lo <= hi)
    {
        var mid = (hi - lo) / 2 + lo;
        var min = mid;

        // 取左中右最小值的下标
        if (mid != hi && a[min] >= a[mid + 1])
            min = mid + 1;
        if (mid != lo && a[min] >= a[mid - 1])
            min = mid - 1;

        if (min == mid)
            return mid;
        if (min > mid)
            lo = min;
        else
            hi = min;
    }

    return -1;
}