Open
Description
习题
出处：LeetCode 算法第74题
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 输出: true示例 2:
输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 输出: false
思路
由于数组是按顺序递增的，所以我们可以通过二分查找法来进行搜索
解答
var searchMatrix = function (matrix, target) {
if (matrix.length == 0) {
return false;
}
var n = matrix.length;
var m = matrix[0].length;
var left = 0;
var right = n * m - 1;
while (left <= right) {
var mid = Math.floor((left + right) / 2);
var current = matrix[Math.floor(mid / m)][mid % m];
if (current == target) {
return true;
} else if (current < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
};Metadata
Assignees
Labels
No labels