题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

注：设二维数组为m行n列。语言：C++

解法1：顺序查找

bool Find(int target, vector<vector<int> > array) { vector<vector<int> >::iterator i; vector<int>::iterator j; vector<int> k; for(i = array.begin(); i != array.end(); ++i) { k = *i; for(j = k.begin(); j != k.end(); ++j) { if(*j == target) return true; } } return false; }

时间复杂度O(mn)，空间复杂度O(1)。

解法2：折半查找

bool Find(int target, vector<vector<int> > array) { if(array.empty()) return false; int row = array.size(); int col = array[0].size(); for(int i = 0; i < row; ++i) { if(array[i].empty()) return false; int low = 0; int high = col-1; if(target == array[i][low]) return true; if(target == array[i][high]) return true; while(low <= high) { int mid = low + (high - low) / 2; if(target == array[i][mid]) return true; else if(target < array[i][mid]) high = mid - 1; else low = mid + 1; } } return false; }

时间复杂度O(mlogn)，空间复杂度O(1)。

解法三：根据数组有序特性，从其右上角元素开始比较。

bool Find(int target, vector<vector<int> > array) { if(array.empty()) return false; int row = array.size(); int col = array[0].size(); int i = 0; int j = col - 1; while((i < row) && (j >= 0)) { if(array[i].empty()) return false; if(target == array[i][j]) return true; else if(target < array[i][j]) j--; else i++; } return false; }

时间复杂度O(m+n)，空间复杂度O(1)