Find Peak Element II

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.

Example

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])

Notes:

1. Follow up "Find Peak Element", from 1D to 2D
2. Must have at least one solution
3. Method 1: Loop all of the elements until find one peak
4. Method 2: Binary Search idea, cut half rows every time
   1. find the middle row
   2. find the largest element in this row
   3. compare it with the element above and below
   4. keep the half which is bigger than it (return it if it is bigger than both of them)
   5. time: O(nLgm)
5. Method 3: same binary search idea, but use row and column in turn

    public List<Integer> findPeakII(int[][] A) {
        List<Integer> result = new ArrayList<>();
        if (A == null || A.length == 0 || A[0] == null || A[0].length == 0) {
            return result;
        }

        int colS = 1;
        int colE = A[0].length-2;
        int rowS = 1;
        int rowE = A.length-2;

        while(colS+1 < colE && rowS+1 < rowE) {
            int rowM = rowS + (rowE-rowS)/2;
            int col = findMaxInRow(A, rowM, colS, colE);
            if (A[rowM][col] < A[rowM-1][col]) {
                rowE = rowM;
            } else if (A[rowM][col] < A[rowM+1][col]) {
                rowS = rowM;
            } else {
                result.add(rowM);
                result.add(col);
                return result;
            }

            int colM = colS + (colE-colS)/2;
            int row = findMaxInColumn(A, colM, rowS, rowE);
            if (A[row][colM] < A[row][colM-1]) {
                colE = colM;
            } else if (A[row][colM] < A[row][colM+1]) {
                colS = colM;
            } else {
                result.add(row);
                result.add(colM);
                return result;
            }
        }

        if (A[rowS][colS] > A[rowE][colE]) {
            result.add(rowS);
            result.add(colS);
        } else {
            result.add(rowE);
            result.add(colE);
        }

        return result;
    }

    private int findMaxInColumn(int[][] A, int column, int start, int end) {
        int max = A[start][column];
        int row = start;
        for (int i = start+1; i <= end; ++i) {
            if (max < A[i][column]) {
                max = A[i][column];
                row = i;
            }
        }

        return row;
    }

    private int findMaxInRow(int[][] A, int row, int start, int end) {
        int max = A[row][start];
        int col = start;
        for (int i = start+1; i <= end; ++i) {
            if (max < A[row][i]) {
                max = A[row][i];
                col = i;
            }
        }

        return col;
    }