为什么二进制搜索适用于这个未排序的数组？

Question

给出这个问题： 峰值元素是大于其相邻元素的元素。

给定一个输入数组，其中 num[i] ≠ num[i+1]，找到一个峰值元素和 return 它的索引。

数组可能包含多个峰，在这种情况下return任何一个峰的索引都可以。

示例：数组 = [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

如果有多个峰则数组不需要排序。排序实际上会删除除一个峰以外的所有峰。

这段代码是如何工作的？想象一下，您正走在崎岖不平的道路上，需要找到一个高峰 - 但您是盲人，所以您看不到它，只能凭感觉来工作。你从某个点开始，然后根据你所在点的斜率检查你是否必须向左或向右走（你把一只脚向左和向右，然后感受你所击中的东西）。然后你迈出一大步（你 Miss Fantastic 所以大步对你来说不是问题）并再次检查新位置的坡度。您以减小的步长重复此操作，直到达到左右下坡的点，因此您已达到顶峰。

Answer 2

如果 "peak" 的定义仅仅是它是一个比周围元素大的元素，那么你可以推断出它为什么有效。

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

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

条件是：

如果中间元素比相邻元素大，它可能是峰值 - 它肯定比右边的元素大。在 "left hand" 一半内搜索至少同样大的峰值。
否则，相邻的元素可能是峰 - 它肯定比左边的元素大。在 "right hand" 一半中搜索至少同样大的峰值。

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

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

您继续，直到 left == right，此时您知道您已经到达顶峰，因为相邻元素较少（或者您位于数组的一端或另一端）。

为什么二进制搜索适用于这个未排序的数组？

Why does binary search work for this unsorted array?

java

arrays

recursion

binary-search