• ㊗️
• 大家
• 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