1.4.18

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

解答

和二分查找的方式类似,先确认中间的值是否是局部最小,如果不是,则向较小的一侧二分查找。
在三个数中比较得到最小值需要两次比较,因此最坏情况下为 $ ~2\lg N $ 次比较。

代码

using System;

namespace _1._4._18
{
    class Program
    {
        static void Main(string[] args)
        {
            var a = new int[5] { 1, 2, 5, 3, 5 };
            Console.WriteLine(LocalMinimum(a));
        }

        /// <summary>
        /// 寻找数组的局部最小元素。
        /// </summary>
        /// <param name="a">寻找范围。</param>
        /// <returns>局部最小元素的值。</returns>
        static int LocalMinimum(int[] a)
        {
            int lo = 0;
            int hi = a.Length - 1;
            while (lo <= hi)
            {
                int mid = (hi - lo) / 2 + lo;
                int 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;
        }
    }
}
上一题 下一题