算法题 寻找 MountainArray 的 peek 求解惑

[amiwrong123]

其实这个题是 https://leetcode-cn.com/problems/find-in-mountain-array/ 的一部分： 比如，array = [1,2,3,4,5,3,1]，这个数组是由严格递增和严格递减的两个有序数组构成的，它的 peek 就是 5. 现在我改一下条件，要么这个数组是严格递增和严格递减的两个有序数组构成的（这种情况返回 peek 的索引），要么这个数组就只是一个严格递增或严格递减的数组（返回-1 ）。

很明显，寻找 peek 可以用二分查找。

然后我发现这个算法有两种写法：

    public int findArrayPeek(int[] array) {
        int low = 0, high = array.length-1;

        int middle = -1;
        while (low <= high && (middle = (low + high)/2)-1 > 0 && middle+1 < array.length) {
            if (array[middle-1] < array[middle] && array[middle] > array[middle+1]) {
                return middle;
            } else if (array[middle-1] < array[middle] && array[middle] < array[middle+1]) {
                low = middle+1;
            } else {
                high = middle-1;
            }
        }

        return -1;
    }

    @Test
    public void findArrayPeekTest() {
        int[] array = {1,2,3,4,5,3,1};
        System.out.println(findArrayPeek(array));
        int[] array1 = {0,1,2,4,2,1};
        System.out.println(findArrayPeek(array1));
        int[] array2 = {0,1,2,4,5,1};
        System.out.println(findArrayPeek(array2));
        int[] array3 = {0,1,2,4,5,6};
        System.out.println(findArrayPeek(array3));
        int[] array4 = {6,5,4,3,2,1};
        System.out.println(findArrayPeek(array4));
    }

首先是标准的二分查找，但循环条件中必须要上索引的保护。

    public int findArrayPeek1(int[] array) {
        int low = 0, high = array.length-1;
        
        while (low < high-1) {
            int middle = (low + high)/2;
            if (array[middle-1] < array[middle] && array[middle] > array[middle+1]) {
                return middle;
            } else if (array[middle-1] < array[middle] && array[middle] < array[middle+1]) {
                low = middle;
            } else {
                high = middle;
            }
        }

        return -1;
    }

    @Test
    public void findArrayPeek1Test() {
        int[] array = {1,2,3,4,5,3,1};
        System.out.println(findArrayPeek1(array));
        int[] array1 = {0,1,2,4,2,1};
        System.out.println(findArrayPeek1(array1));
        int[] array2 = {0,1,2,4,5,1};
        System.out.println(findArrayPeek1(array2));
        int[] array3 = {0,1,2,4,5,6};
        System.out.println(findArrayPeek1(array3));
        int[] array4 = {6,5,4,3,2,1};
        System.out.println(findArrayPeek1(array4));
    }

然后是另外一种写法如上，它的处理过程从low = middle+1;变成了low = middle;，这里循环条件也必须得变，但这里不用加索引保护。

这两个算法，变化的只有对 low high 的处理，和循环条件。但感觉原理有点不一样，但我又说不清楚。。。（这种说不清楚的感觉，应该是我没有彻底弄懂~）

或者说，对 low high 的处理怎么影响这个过程的，相应的循环条件应该怎么写？

看了这道题的视频题解，发现二分查找的很多细节我都没搞懂。。

[hitmanx]

"要么这个数组是严格递增和严格递减的两个有序数组构成的（这种情况返回 peek 的索引），要么这个数组就只是一个严格递增或严格递减的数组（返回-1 ）。"

没看明白，你增加的这两种情况头尾判断一下(O(1))就能知道吧，比如
For A[n], n >= 3,
if A[1] > A[0]:
....if A[n-2] > A[n-1]: MoutainArray
....else: 单调递增
else: 单调递减

[amiwrong123]

@hitmanx
那啥，你得返回 peek 的索引呀，你这样只是判断这是哪种数组。。在这道 LeetCode 题里面，也是先需要获得 peek 的索引的。

[hitmanx]

@amiwrong123 我的意思是按照我的理解，你增加的额外几种情况，其实一个 O(1)的判断就完成了，剩下的又回到了原来的题目，所以并没有给题目带来任何实际的变化，比如:

if (A[1] < A[0]):
.... return -1 # monotone decreasing

if (A[n-2] < A[n-1]):
.... return -1 # monotone increasing

// same old code that finds the index within a mountain array

[amiwrong123]

@hitmanx
好吧，懂你意思啦。确实是这样的，相当于你提前判断特殊情况，然后就不用执行二分查询代码了。不过我重点还是在于这个二分查找的写法

[binux]

原理没有不一样啊，就是边界处理细节不同罢了。
二分本来就是有“自适应性”的，只要趋势和终结条件是对的，边界多一个少一个没有关系。