两次二分,一次AC,注意越界的问题。
using namespace std; class Solution { public: bool searchMatrix(vector<vector<int> > &matrix, int target) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. if(matrix.size() <= 0) return false; if(target > matrix[matrix.size()-1][matrix[0].size()-1]) return false; vector<int>cols(matrix.size()); for(int i = 0;i < matrix.size();i++) { cols[i] = matrix[i][matrix[0].size()-1]; } int colindex = bsearch(0,(int)(matrix.size()),cols,target); if(colindex == -1) return true; int rowindex = bsearch(0,(int)(matrix[colindex].size()),matrix[colindex],target); if(rowindex == -1) return true; return false; } int bsearch(int left,int right,vector<int> seq,int target) { if(left > right) { return right + 1; } int mid = (left + right) / 2; if(seq[mid] == target) { return -1; } else if(seq[mid] < target) { return bsearch(mid+1,right,seq,target); } else { return bsearch(left,mid-1,seq,target); } } };