/**
* Write an efficient algorithm that searches for a value target in an m x n
* integer matrix matrix. This matrix has the following properties:
* <p>
* <p>
* Integers in each row are sorted in ascending from left to right.
* Integers in each column are sorted in ascending from top to bottom.
* <p>
* <p>
* <p>
* Example 1:
* <p>
* <p>
* 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
* <p>
* <p>
* Example 2:
* <p>
* <p>
* 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 = 20
* Output: false
* <p>
* <p>
* <p>
* Constraints:
* <p>
* <p>
* m == matrix.length
* n == matrix[i].length
* 1 <= n, m <= 300
* -10⁹ <= matrix[i][j] <= 10⁹
* All the integers in each row are sorted in ascending order.
* All the integers in each column are sorted in ascending order.
* -10⁹ <= target <= 10⁹
* <p>
* Related Topics数组 | 二分查找 | 分治 | 矩阵
* <p>
* 👍 1130, 👎 0
*/
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
for (int[] row : matrix) {
int index = search(row, target);
if (index >= 0) {
return true;
}
}
return false;
}
public int search(int[] nums, int target) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
int num = nums[mid];
if (num == target) {
return mid;
} else if (num > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
}
//leetcode submit region end(Prohibit modification and deletion)
