74. 搜索二维矩阵

方法一：两次二分查找

1. class Solution {
2. public:
3.     bool searchMatrix(vector<vector<int>> matrix, int target) {
4.         auto row = upper_bound(matrix.begin(), matrix.end(), target, [](const int b, const vector<int> &a) {
5.             return b < a[0];
6.         });
7.         if (row == matrix.begin()) {
8.             return false;
9.         }
10.         --row;
11.         return binary_search(row->begin(), row->end(), target);
12.     }
13. };

复制代码

方法二：一次二分查找 

1. class Solution {
2. public:
3.     bool searchMatrix(vector<vector<int>>& matrix, int target) {
4.         int m = matrix.size(), n = matrix[0].size();
5.         int low = 0, high = m * n - 1;
6.         while (low <= high) {
7.             int mid = (high - low) / 2 + low;
8.             int x = matrix[mid / n][mid % n];
9.             if (x < target) {
10.                 low = mid + 1;
11.             } else if (x > target) {
12.                 high = mid - 1;
13.             } else {
14.                 return true;
15.             }
16.         }
17.         return false;
18.     }
19. };

复制代码

leetcode题解

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。