1.4.20

1.4.20 #

解答 #

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

我们使用这个类生成双调数组，并使用其中的 Max() 方法找到双调数组的最大值。

找到最大值之后分别对左右两侧进行二分查找，注意对于升序和降序的数组二分查找的实现有所不同。

代码 #

BitonicMax 类 #

public class BitonicMax
{
    /// <summary>
    /// 生成双调数组。
    /// </summary>
    /// <param name="n">数组的大小。</param>
    /// <returns></returns>
    public static int[] Bitonic(int n)
    {
        var random = new Random();
        var mid = random.Next(n);
        var a = new int[n];
        for (var 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 (var 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;
        }
        var 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;
    }
}

主程序 #

var a = BitonicMax.Bitonic(100);
var max = BitonicMax.Max(a, 0, a.Length - 1);
var key = a[50];
var leftSide = BinarySearchAscending(a, key, 0, max);
var 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");
}

static int BinarySearchAscending(int[] a, int key, int lo, int hi)
{
    while (lo <= hi)
    {
        var 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;
}

static int BinarySearchDescending(int[] a, int key, int lo, int hi)
{
    while (lo <= hi)
    {
        var 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