LeetCode Brushing Diary: 74. Searching 2D Matrix

编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值.该矩阵具有如下特性：

每行中的整数从左到右按升序排列.
每行的第一个整数大于前一行的最后一个整数.

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

思路：

因为是有序的,So first arrange the last number of each line to compare with the target,Find out if the target is in the range of the current row,不在,then loop to the next line,直到找到为止,找到当前行,Then use a binary search algorithm to find if there is a target in that row.

题解：

class Solution {
    
    public boolean searchMatrix(int[][] matrix, int target) {
    
        int m = matrix.length;
        int n = matrix[0].length;
        int x = 0;
        for (int i = 0; i < m; i++) {
    
            if(matrix[i][n-1] >= target){
    
                x = i;
                break;
            }
        }
        int start = 0, end = n-1;
        while (start <= end){
    
            int mid = (start + end)/2;
            if(matrix[x][mid] == target){
    
                return true;
            }else if(matrix[x][mid] > target){
    
                end = mid - 1;
            }else {
    
                start = mid + 1;
            }
        }
        return false;
    }
}