不知从什么时候开始，总觉的编程似乎离算法很远了，但是最近发觉这种想法和可怕，如果只当代码的搬运工，想想是那么可怕，思来想去后悔至极，就像每天总结一点，收获一点。于是就想起之前的剑指offer上的题目，于是做完了，总结一下。
题目：
二维数组中的查找
题目描述：
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
题目要求：
时间限制：1秒 空间限制：32768K
题目分析：
我们从题干可以知道，这个二维的数组是有规律有序的，每一行每一列都是按大小顺序排列好的。
思路一：
我们拿到题目的第一眼，绝大多数人想到的肯定是循环遍历，遍历比对，这样其实就是最没有技术含量的操作，是最浪费时间和空间的方法，耗时费力，但是确实最不用动脑子的。
思路二：
按照列或者行，循环的用二分法不断找到行和列的中间值，不断和目标数比对，这样比全部遍历的复杂度少1/2，但是还是存在多层的嵌套循环，这样就会造成时间和空间复杂度的加剧。
思路三：
我们仔细从题目所提供的信息入手，发觉这个数组或者矩阵是非常有规律的：
image.png
假如存在这样的数组，那我们该这样来看，
image.png
我们可以看到一个数的上面总是比自己小，右边总是比自己大，那我们就可以将其近似的看成一棵二叉树，通过二叉树的性质来查找是否存在这个数。
那么我们代码的思路就有了：
找到左下角的节点当作根节点，判断target是否比它大，比它大就向右移动，比它小就向上移动，以此此循环不断在根节点的左右子树上面判断。
代码就是这个思路写出来的：
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int rows = array.size();
int cols = array[0].size();
bool find = false;
int i = rows - 1;
int j = 0;
while(j < cols && i >= 0){
if(array[i][j] > target){
i--;
}else if(array[i][j] < target){
j++;
}else{
return true;
}
}
return false;
}
};
2018年2月1日
