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
Solution 1
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function(matrix, target) {
var row = searchRow(matrix, target, 0, matrix.length - 1);
return row === -1 ? false : searchArray(matrix[row], target, 0, matrix[row].length - 1);
};
var searchRow = function (matrix, target, top, bottom) {
if (top > bottom) return -1;
var mid = top + Math.floor((bottom - top) / 2);
var len = matrix[mid].length;
if (len === 0) return -1;
if (matrix[mid][0] <= target && target <= matrix[mid][len - 1]) {
return mid;
} else if (target < matrix[mid][0]) {
return searchRow(matrix, target, top, mid - 1);
} else {
return searchRow(matrix, target, mid + 1, bottom);
}
};
var searchArray = function (arr, target, left, right) {
if (left > right) return false;
var mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) {
return true;
} else if (arr[mid] > target) {
return searchArray(arr, target, left, mid - 1);
} else {
return searchArray(arr, target, mid + 1, right);
}
};
Explain:
先找行，再找列。
Complexity:
- Time complexity : O(log(m) + log(n)).
n行m列。 - Space complexity : O(1).
Solution 2
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function(matrix, target) {
var n = matrix.length;
var m = (matrix[0] || []).length;
var ll = 0;
var rr = (n * m) - 1;
var mid = 0;
var tmp = 0;
while (ll <= rr) {
mid = ll + Math.floor((rr - ll) / 2);
tmp = matrix[Math.floor(mid / m)][mid % m];
if (tmp === target) {
return true;
} else if (tmp > target) {
rr = mid - 1;
} else {
ll = mid + 1;
}
}
return false;
};
Explain:
直接找位置。
Complexity:
- Time complexity : O(log(m*n)).
n行m列。 - Space complexity : O(1).