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:
|
1 2 3 4 5 6 7 8 |
<strong>Input:</strong> matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 <strong>Output:</strong> true |
Example 2:
|
1 2 3 4 5 6 7 8 |
<strong>Input:</strong> matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 <strong>Output:</strong> false |
Solution: Binary Search
Treat the 2D array as a 1D array. matrix[index / cols][index % cols]
Time complexity: O(log(m*n))
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty()) return false; int l = 0; int r = matrix.size() * matrix[0].size(); const int cols = matrix[0].size(); while (l < r) { const int m = l + (r - l) / 2; if (matrix[m / cols][m % cols] == target) { return true; } else if (matrix[m / cols][m % cols] > target) { r = m; } else { l = m + 1; } } return false; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment