1.4.20

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

解答

首先给出 BitMax 类的官方 Java 实现:BitonicMax.java

我们使用这个类生成双调数组,并使用其中的 Max() 方法找到双调数组的最大值。
找到最大值之后分别对左右两侧进行二分查找,注意对于升序和降序的数组二分查找的实现有所不同。

代码

BitonicMax 类

using System;

namespace _1._4._20
{
    /// <summary>
    /// 双调查找类。
    /// </summary>
    public class BitonicMax
    {
        /// <summary>
        /// 生成双调数组。
        /// </summary>
        /// <param name="N">数组的大小。</param>
        /// <returns></returns>
        public static int[] Bitonic(int N)
        {
            Random random = new Random();
            int mid = random.Next(N);
            int[] a = new int[N];
            for (int i = 1; i < mid; ++i)
            {
                a[i] = a[i - 1] + 1 + random.Next(9);
            }

            if (mid > 0)
            {
                a[mid] = a[mid - 1] + random.Next(10) - 5;
            }

            for (int i = mid + 1; i < N; ++i)
            {
                a[i] = a[i - 1] - 1 - random.Next(9);
            }

            return a;
        }

        /// <summary>
        /// 寻找数组中的最大值。
        /// </summary>
        /// <param name="a">查找范围。</param>
        /// <param name="lo">查找起始下标。</param>
        /// <param name="hi">查找结束下标。</param>
        /// <returns>返回数组中最大值的下标。</returns>
        public static int Max(int[] a, int lo, int hi)
        {
            if (lo == hi)
            {
                return hi;
            }
            int mid = lo + (hi - lo) / 2;
            if (a[mid] < a[mid + 1])
            {
                return Max(a, mid + 1, hi);
            }
            if (a[mid] > a[mid + 1])
            {
                return Max(a, lo, mid);
            }
            return mid;
        }
    }
}

主程序

using System;

namespace _1._4._20
{
    /*
     * 1.4.20
     * 
     * 双调查找。
     * 如果一个数组中的所有元素是先递增后递减的,则称这个数组为双调的。
     * 编写一个程序,给定一个含有 N 个不同 int 值的双调数组,判断它是否含有给定的整数。
     * 程序在最坏情况下所需的比较次数为 ~3lgN
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            int[] a = BitonicMax.Bitonic(100);
            int max = BitonicMax.Max(a, 0, a.Length - 1);
            int key = a[50];
            int leftside = BinarySearchAscending(a, key, 0, max);
            int rightside = BinarySearchDescending(a, key, max, a.Length - 1);

            if (leftside != -1)
            {
                Console.WriteLine(leftside);
            }
            else if (rightside != -1)
            {
                Console.WriteLine(rightside);
            }
            else
            {
                Console.WriteLine("No Result");
            }
        }

        /// <summary>
        /// 对升序数组的二分查找。
        /// </summary>
        /// <param name="a">升序数组。</param>
        /// <param name="key">关键值。</param>
        /// <param name="lo">查找的左边界。</param>
        /// <param name="hi">查找的右边界。</param>
        /// <returns>返回找到关键值的下标,如果没有找到则返回 -1。</returns>
        static int BinarySearchAscending(int[] a, int key, int lo, int hi)
        {
            while (lo <= hi)
            {
                int mid = lo + (hi - lo) / 2;

                if (a[mid] < key)
                {
                    lo = mid + 1;
                }
                else if (a[mid] > key)
                {
                    hi = mid - 1;
                }
                else
                {
                    return mid;
                }
            }

            return -1;
        }

        /// <summary>
        /// 对降序数组的二分查找。
        /// </summary>
        /// <param name="a">升序数组。</param>
        /// <param name="key">关键值。</param>
        /// <param name="lo">查找的左边界。</param>
        /// <param name="hi">查找的右边界。</param>
        /// <returns>返回找到关键值的下标,如果没有找到则返回 -1。</returns>
        static int BinarySearchDescending(int[] a, int key, int lo, int hi)
        {
            while (lo < hi)
            {
                int mid = lo + (hi - lo) / 2;

                if (a[mid] > key)
                {
                    lo = mid + 1;
                }
                else if (a[mid] < key)
                {
                    hi = mid - 1;
                }
                else
                {
                    return mid;
                }
            }

            return -1;
        }
    }
}

另请参阅

BitonicMax.java

上一题 下一题