Leetcode 240. search two-dimensional matrix II medium

---

1.Description

Write an efficient algorithm to search m x n matrix matrix One of the goals in target . The matrix has the following characteristics ：

The elements of each row are arranged in ascending order from left to right .
The elements of each column are arranged in ascending order from top to bottom .

---

2.Example

 Input ：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
 Output ：true

---

3.Solution

1.

Start from the lower left corner of the matrix , If target>matrix[row][col] Just move to the right , If target<matrix[row][col] Just move up .
Time complexity ：O（m+n）

    public boolean searchMatrix(int[][] matrix, int target) {
    
        int m = matrix.length;
        int n = matrix[0].length;
        int row = m-1;
        int col = 0;
        while(row>=0&&col<=n-1) {
    
        	if(target>matrix[row][col]) {
    
        		col++;
        	}else if(target<matrix[row][col]) {
    
        		row--;
        	}else {
    
        		return true;
        	}
        }
        return false;
    }

2. recursive

Divide the matrix into four parts , Upper left is less than target, The lower right is greater than target,target Included in the upper right and lower left , Recursively divide the upper right and lower left respectively .....
Time complexity ：O（nlogn）

class Solution {
    
    private int[][] matrix;
    private int target;

    private boolean searchRec(int left, int up, int right, int down) {
    
        // this submatrix has no height or no width.
        if (left > right || up > down) {
    
            return false;
        // `target` is already larger than the largest element or smaller
        // than the smallest element in this submatrix.
        } else if (target < matrix[up][left] || target > matrix[down][right]) {
    
            return false;
        }

        int mid = left + (right-left)/2;

        // Locate `row` such that matrix[row-1][mid] < target < matrix[row][mid]
        int row = up;
        while (row <= down && matrix[row][mid] <= target) {
    
            if (matrix[row][mid] == target) {
    
                return true;
            }
            row++;
        }

        return searchRec(left, row, mid-1, down) || searchRec(mid+1, up, right, row-1);
    }

    public boolean searchMatrix(int[][] mat, int targ) {
    
        // cache input values in object to avoid passing them unnecessarily
        // to `searchRec`
        matrix = mat;
        target = targ;

        // an empty matrix obviously does not contain `target`
        if (matrix == null || matrix.length == 0) {
    
            return false;
        }

        return searchRec(0, 0, matrix[0].length-1, matrix.length-1);
    }
}