题目描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
自己的思路实在是傻×了，先看下正确思路吧
把当前数字定位在第一行，最后一列。如果数字小则增大行，如果数字大则减小列！O(M+N)
bool Find3(vector<vector<int> > array,int target) { if(array.empty() && array[0].empty()) return false; int r = 0, c = array[0].size() - 1; while(r < array.size() && c >= 0) { if(array[r][c] == target) return true; else if(array[r][c] > target) c--; else r++; } return false; }
我自己二分查找的思路，每次扔掉一半O(log(MN)),超级繁琐，也AC了
bool Find(vector<vector<int> > array,int target) { if(array.empty() && array[0].empty()) return false; //用四个变量标记剩余的查找范围 int cleft = 0, cright = array[0].size() - 1; int rup = 0, rdown = array.size() - 1; int l, r, u, d; while(cleft <= cright && rup <= rdown) { //对限定区域的第一行进行二分查找，定位刚好小于target值的列 l = cleft, r = cright; if(array[rup][l] > target) //所有的都大于target return false; else { while(l <= r) { int m = l + (r - l) / 2; if(array[rup][m] == target) return true; else if(array[rup][m] < target) l = m + 1; else r = m - 1; } cright = r; } //对限定区域的第一列进行二分查找，定位刚好小于target值的行 u = rup, d = rdown; if(array[u][cleft] > target) //所有的都大于target return false; else { while(u <= d) { int m = u + (d - u) / 2; if(array[m][cleft] == target) return true; else if(array[m][cleft] < target) u = m + 1; else d = m - 1; } rdown = d; } //对限定区域的最后一行进行二分查找，定位刚好大于target值的列 l = cleft, r = cright; if(array[rdown][r] < target) //所有的都小于target return false; else { while(l <= r) { int m = l + (r - l) / 2; if(array[rdown][m] == target) return true; else if(array[rdown][m] < target) l = m + 1; else r = m - 1; } cleft = l; } //对限定区域的最后一列查找，定位刚好大于target值的行 u = rup, d = rdown; if(array[d][cright] < target) //所有的都小于target return false; else { while(u <= d) { int m = u + (d - u) / 2; if(array[m][cright] == target) return true; else if(array[m][cright] < target) u = m + 1; else d = m - 1; } rup = u; } } return false; //没找到 }