为什么二进制搜索对这个无序数组有效？

Question

考虑到这个问题：峰值元素是一个大于相邻元素的元素。

给定一个输入数组，其中num[i]≠ num[i 1]，找到一个peak元素并返回其索引。

该数组可以包含多个峰值，在那种情况下将索引返回到任何一个峰值都是精细的。

示例：Array=[1,4,5,7,4,3,1]。峰值指数=3（即7）。

下面的代码非常有效（不仅仅适用于此测试用例）：

    public static int getPeakElement(int[] array, int left, int right) {

    if (left == right) {
        return left;
    }

    int mid = (left + right) / 2;

    if (array[mid] > array[mid + 1]) {
        return getPeakElement(array, left, mid);
    }

    return getPeakElement(array, mid + 1, right);
}   

我不明白它是如何工作的——我以为二进制搜索只是用于排序数组/旋转数组。

Answer 1

如果有多个峰值，则不需要对数组进行排序。排序实际上会去除除一个峰值以外的所有峰值。

这个代码是如何工作的？想象一下，你在一条崎岖不平的路上，需要找到一座山峰——但你是盲人，所以你看不见它，只能凭感觉工作。你从某个点开始，根据你所处点的坡度，检查你是否必须向左或向右移动（你向左和向右移动一只脚，感觉你击中了什么）。然后你迈出一大步（你是神奇小姐，所以huuge steps对你来说不是问题），再次检查新位置的坡度。你重复这一步，减小步长，直到你到达一个点，左右都是下坡，所以你达到了一个峰值。

Answer 2

如果“峰值”的定义仅仅是它是一个比周围元素大的元素，那么你可以解释它为什么工作。

if (array[mid] > array[mid + 1]) {
    return getPeakElement(array, left, mid);
}

return getPeakElement(array, mid + 1, right);

条件是：

• 如果中间的元素比相邻的元素大，它可能是峰值——它肯定比右边的元素大。在“左手”的一半范围内搜索一个至少同样大的峰值

随着递归的进行，您知道：

• 左-1在数组之外，或者那里的元素小于arr[左]处的元素（否则你不会选择这一半）
• right 1在数组之外，或者那里的元素小于arr[right]处的元素（否则你不会选择这一半）。

你继续，直到↓==right，这时你知道你已经到达了峰值，因为相邻的元素更少（或者你在数组的一端或另一端）。