前言
本文只供自己学习做笔记留存，未经过很详细的梳理。谨慎阅读！！！
描述
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
给定 target = 7，返回 true。
给定 target = 3，返回 false。
数据范围：矩阵的长宽满足 0≤n,m≤5000≤n,m≤500 ， 矩阵中的值满足 0≤val≤10^9
进阶：空间复杂度 O(1) ，时间复杂度 O(n+m)
例子
7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]] 返回true
1,[[2]] 返回 false
方法1:暴力循环，（13ms,1191kb）
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param target int整型 * @param array int整型vector<vector<>> * @return bool布尔型 */ //时间复杂度 O(n*n) bool Find(int target, vector<vector<int> >& array) { if(array.empty())return false; //如果为空直接返回false for(int row = 0;row<array.size();++row){ auto tempele = array[row]; if(tempele.empty())continue; for(const auto currval :tempele){ if(currval == target) return true; } } return false; // write code here } };
方法2： 二分法，（13ms，1184kb）
- 左闭右闭
- while(left<=right) 为何使用<= ，因为闭区间里left==right有效
- if(nums[middle]>target)right=middle - 1;因为第middle个值在此不等于target，所以右边界赋值时索引用midle-1。
#include <vector> class Solution { public: //二分查找 bool search(int target,vector<int> array){ //采用左闭右闭解法 int left = 0; int right = array.size() - 1; while(left<=right){ int middle = left +( (right - left)/2); if(array[middle]>target){ right = middle - 1; }else if(array[middle]<target){ left = middle + 1; }else{ return true; } } return false; } /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param target int整型 * @param array int整型vector<vector<>> * @return bool布尔型 */ //时间复杂度 O(n*n) bool Find(int target, vector<vector<int> >& array) { if(array.empty())return false; //如果为空直接返回false for(int row = 0;row<array.size();++row){ auto tempele = array[row]; if(search(target,tempele))return true; } return false; // write code here } };
总结
本题的数据都是有序的，很明显可以用二分法。更深一步的学习了二分法的细节。防止混淆以后只用一种：左闭右闭的二分法。
