https://www.lintcode.com/problem/find-peak-element-ii

FindPeak.java

public class Solution {
    /*
     * @param A: An integer matrix
     * @return: The index of the peak
     */
    public List<Integer> findPeakII(int[][] A) {
        // write your code here
        if (A == null || A.length < 3 || A[0].length < 3) {
            return new LinkedList<>();
        }
        
        return findPeakInRect(A, 0, A.length - 1, 0, A[0].length - 1);
    }
    
    private List<Integer> findPeakInRect(int[][] A, int startRow, int endRow, int startCol, int endCol) {
        if (startRow == endRow && startCol == endCol) {
            return Arrays.asList(startRow, startCol);
        }
        
        int midRow = startRow + (endRow - startRow) / 2;
        int midCol = startCol + (endCol - startCol) / 2;
        
        int maxColIndex = findMaxIndexInRow(A, midRow);
        int maxRowIndex = findMaxIndexInCol(A, midCol);
        
        if (maxRowIndex == midRow && maxColIndex == midCol) {
            // Peak is at the center of the middle lines
            return Arrays.asList(midRow, midCol);
        }
        
        if (A[midRow][maxColIndex] >= A[maxRowIndex][midCol]) {
            if (maxColIndex > midCol) {
                // Peak is at the right section of the matrix
                startCol = midCol;
            } else {
                // Peak is at the left section of the matrix
                endCol = midCol;
            }
            
            if (A[midRow - 1][maxColIndex] < A[midRow][maxColIndex] && 
                A[midRow][maxColIndex] < A[midRow + 1][maxColIndex]) {
                // Peak is at the bottom section of the matrix
                startRow = midRow;
                return findPeakInRect(A, midRow, endRow, startCol, endCol);
            }
            
            if (A[midRow - 1][maxColIndex] > A[midRow][maxColIndex] && 
                A[midRow][maxColIndex] > A[midRow + 1][maxColIndex]) {
                // Peak is at the top section of the matrix
                return findPeakInRect(A, startRow, midRow, startCol, endCol);
            }
            
            return Arrays.asList(midRow, maxColIndex);
        }
        
        
        if (maxRowIndex > midRow) {
            // Peak is at the right section of the matrix
            startRow = midRow;
        } else {
            // Peak is at the left section of the matrix
            endRow = midRow;
        }
        
        if (A[maxRowIndex][midCol - 1] < A[maxRowIndex][midCol] && 
            A[maxRowIndex][midCol] < A[maxRowIndex][midCol + 1]) {
            // Peak is at the right section of the matrix
            return findPeakInRect(A, startRow, endRow, midCol, endCol);
        }
        
        if (A[maxRowIndex][midCol - 1] > A[maxRowIndex][midCol] && 
            A[maxRowIndex][midCol] > A[maxRowIndex][midCol + 1]) {
            // Peak is at the left section of the matrix
            return findPeakInRect(A, startRow, endRow, startCol, midCol);
        }
        
        return Arrays.asList(maxRowIndex, midCol);
    }
    
    private int findMaxIndexInRow(int[][] nums, int row) {
        int maxColIndex = 0;
        for (int col = 1; col < nums[row].length; col++) {
            if (nums[row][col] > nums[row][maxColIndex]) {
                maxColIndex = col;
            }
        }
        return maxColIndex;
    }
    
    private int findMaxIndexInCol(int[][] nums, int col) {
        int maxRowIndex = 0;
        for (int row = 1; row < nums.length; row++) {
            if (nums[row][col] > nums[maxRowIndex][col]) {
                maxRowIndex = row;
            }
        }
        return maxRowIndex;
    }
}