74. Search a 2D Matrix

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.

The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true

Example 2:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

Code

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0) return false;
        if(matrix[0] == null || matrix[0].length == 0) return false;

        int row = matrix.length;
        int col = matrix[0].length;
        int start = 0;
        int end = row * col - 1;

        while(start + 1 < end){
            int mid = (end - start) / 2 + start;
            int value = matrix[mid / col][mid % col];
            if(value == target) {
                return true;
            } else if(value < target){
                start = mid;
            } else {
                end = mid;
            }
        }

        if(matrix[start / col][start % col] == target){
            return true;
        } else if (matrix[end / col][end % col] == target){
            return true;
        } else {
            return false;
        }
    }
}

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or matrix and not matrix[0]:
            return False

        row = len(matrix)
        col = len(matrix[0])

        start = 0
        end = row * col - 1

        while start + 1 < end:
            mid = (start + end) // 2
            num = matrix[mid // col][mid % col]

            if num == target:
                return True
            elif num > target:
                end = mid
            else:
                start = mid

        if matrix[start // col][start % col] == target:
            return True

        if matrix[end // col][end % col] == target:
            return True

        return False