Find Peak Element II(Hard)

There is an integer matrix which has the following features:

The numbers in adjacent positions are different. The matrix has n rows and m columns.

• For all i < m, A[0][i] < A[1][i] && A[n - 2][i] > A[n - 1][i].
• For all j < n, A[j][0] < A[j][1] && A[j][m - 2] > A[j][m - 1]
• We define a position P is a peek if A[j][i] > A[j+1][i] && A[j][i] > A[j-1][i] && A[j][i] > A[j][i+1] && A[j][i] > A[j][i-1].

Find a peak element in this matrix. Return the index of the peak.

Given a matrix:

[
  [1 ,2 ,3 ,6 ,5],
  [16,41,23,22,6],
  [15,17,24,21,7],
  [14,18,19,20,10],
  [13,14,11,10,9]
]
return index of 41 (which is [1,1]) or index of 24 (which is [2,2])

最直观的方法是遍历整个矩阵，但这要O(MN)的时间。对于二维数组，我们也可以使用二分搜索法。比如，我们按照行二分搜索（意思是在1、2、3、4、5行中取得第3行），然后遍历这行找到这行的峰值，比如第3行是24。然后看24的上下两个元素的大小，这里24比19大，但是比25小，可知1、2行中肯定有答案（因为24到25是一个上坡，上坡方向必有解）。所以我们抛弃第3、4、5行，再在1、2行中重复这个二分搜索，直到找到结果。

public List<Integer> findPeakII(int[][] A) {
        // write your code here
        List<Integer> res = new ArrayList<Integer>();
        int min = 0, max = A.length - 1, mid = max / 2;
        while(min <= max){
            //对行进行二分
            mid = min + ((max - min) >> 1);
            //找出中间行的峰值
            int col = findPeak(mid, A);
            //判断二分前进方向
            if(A[mid][col] < A[mid + 1][col]){
                min = mid + 1;
            } else if (A[mid][col] < A[mid - 1][col]){
                max = mid - 1;
            } else {
            //四周都较小则返回结果
                res.add(mid);
                res.add(col);
                return res;
            }
        }
        return res;
    }

    private int findPeak(int row, int[][] A){
        int peak = 0;
        for(int i = 1; i < A[row].length; i++){
            if(A[row][i]>A[row][peak]){
                peak = i;
            }
        }
        return peak;
    }