28 · 搜索二维矩阵

LintCode 炼码

class Solution {
public:/* @param matrix: matrix, a list of lists of integers* @param target: An integer* @return: a boolean, indicate whether matrix contains target*/bool searchMatrix(vector<vector<int>> &matrix, int target) {// write your code hereif (matrix.size() <= 0 || matrix[0].size() <= 0) {return false;}int left = 0;int right = matrix.size() * matrix[0].size()-1;auto get_val = [&matrix](int index) {int row = index / matrix[0].size();int col = index % matrix[0].size();return matrix[row][col];};while (left + 1 < right) {int mid = left + (right-left)/2;if (get_val(mid) == target) {return true;} else if (get_val(mid) > target) {right = mid;} else {left = mid;}}if (get_val(left) == target) {return true;}if (get_val(right) == target) {return true;}return false;}
};