给定一个M*N的二维数组，在每行、或者每列上的元素都是按升序排列的（从小到大），既：matrix[i][j]<matrix[i][j+1];matrix[i][j]<matrix[i+1][j]
要求设计一个算法，在矩阵中查找是否存在给定的值（target）
因为这是一个每行每列的矩阵，我们很快就想到可以对每一行或者每一列进行二分查找，看target是否存在于二维数组中，对M*N二维矩阵，
此算法复杂度为O（M*logN），很容易写出以下代码：
#include <iostream> #include <vector> #include <algorithm> using namespace std; bool findtarget(vector<vector<int> >& matrix, int target){ int m = matrix[0].size() ; int n = matrix.size(); for(int i = 0;i < n;i++){ if(binary_search(matrix[i].begin() ,matrix[i].end(),target)){ //运用STL中的二分查找函数 return true; } } return false; } int main() { int m,n; cin>>m>>n; vector<vector<int> > a; vector<int> line; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ int num; cin>>num; line.push_back(num); } a.push_back(line); } int target; while (1){ cin>>target; bool iffindtarget = findtarget(a,target); if(iffindtarget){ cout<<"true"<<endl; } else{ cout<<"false"<<endl; } } return 0; } 如果不注意的话，很多人一开始会侮辱一个陷阱，设计一个错误的算法：先对行（列）进行二分查找，再对列（行）进行二分查找。既如果目标元素落入第一行（列）的两个元素之间，那么目标元素在两列中小的那列，如果不在，就查找失败。 14 7 11152 5 81219369162210131417241821232630 比如我要查找13是否在矩阵中，先对第一行扫描，13介于11和15之间，则对第四列扫描，13不在第四列中，查找失败。这很明显发生了错误。
另外一种解法是对斜对角线进行扫描，从右上角开始，每走一步往左或往下，历遍对角线可以一次排除一行或一列，复杂度在O（M+N），代码实现如下：
bool searchMatrix(vector<vector<int>>& matrix, int target) { int m = matrix.size(); if (m == 0) return false; int n = matrix[0].size(); int i = 0, j = n - 1; while (i < m && j >= 0) { if (matrix[i][j] == target) return true; else if (matrix[i][j] > target) { j--; } else i++; } return false; }
