二进制搜索双调序列中的最大元素

Question

首先，这个问题的双调数组被定义为这样一个，对于长度为 N 的数组中的某个索引 K，其中 0 < K < N - 1 并且 0 到 K 是一个单调递增的整数序列，并且K到N-1是一个单调递减的整数序列。

示例：[1、3、4、6、9、14、11、7、2、-4、-9]。它从 1 单调递增到 14，然后从 14 递减到 -9。

我担心的是我无法理解用于查找双调序列中最大元素的二进制搜索。

Answer 1

您基本上是在搜索位置 m，以便项目增加到 m，然后从它开始减少。

修改regular binary search可以解决这个问题。

您的搜索在 l 和 r 之间的每次迭代中进行，初始化为 0 和 n - 1，分别。

在每次迭代中，选择 m = ⌊(l + r) / 2⌋。检查 m 的左右邻居（除非 m = 0 或 m = n - 1 ，您只检查一个邻居），然后比较这三个元素。一共有三种情况：

左邻小右邻小- m处的元素就是你要的
左边的邻居小，右边的邻居大-您需要向右搜索。
左边的邻居大，右边的邻居小-你需要向左搜索。

当你向左或向右移动时，你调整 l 和 r 就像通常的二进制搜索一样。

终止与常规二分查找一样，除了以下内容。请注意，如果它终止于您未找到右下邻居的点，则答案为 n - 1；如果它以找到左下邻居而终止，则答案为 0。

Answer 2

Returns给定双调数组中最大元素的索引（先升序，后降序，无重复）：

private int findMax(int[] array, int low, int high) {
    int mid = low + (high-low)/2;

    if (high == low) return high;   // max has be found

    else if (array[mid] < array[mid+1]) {
        return findMax(array, ++mid, high); // search in the right subarray
    } else {
        return findMax(array, low, mid);    // search in the left subarray
    }
}

二进制搜索双调序列中的最大元素

Binay search for maximum element in bitonic sequence

algorithm

binary-search