LeetCode 74 Search a 2D Matrix
概述
https://leetcode.com/problems/search-a-2d-matrix/
二分搜索
实际上就是把一个排好序的列表给 reshape 成了矩阵，所以做一个 idx 映射就好。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int l = 0, r = matrix[0].size() * matrix.size() - 1;
while (l <= r) {
int m = (r - l) / 2 + l;
if (get(matrix, m) == target) {
return true;
} else if (get(matrix, m) < target) {
l = m + 1;
} else { // get(matrix, m) > target
r = m - 1;
}
}
return false;
}
int get(vector<vector<int>>& matrix, int i) {
int n = matrix[0].size();
int r = i / n;
int c = i % n;
return matrix[r][c];
}
};