题目1384：二维数组中的查找
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：7318
解决：1418
- 题目描述：
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
- 输入：
输入可能包含多个测试样例，对于每个测试案例，
输入的第一行为两个整数m和n(1<=m,n<=1000)：代表将要输入的矩阵的行数和列数。
输入的第二行包括一个整数t(1<=t<=1000000)：代表要查找的数字。
接下来的m行，每行有n个数，代表题目所给出的m行n列的矩阵(矩阵如题目描述所示，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
- 输出：
对应每个测试案例，
输出”Yes”代表在二维数组中找到了数字t。
输出”No”代表在二维数组中没有找到数字t。
- 样例输入：
3 3
5
1 2 3
4 5 6
7 8 9
3 3
1
2 3 4
5 6 7
8 9 10
3 3
12
2 3 4
5 6 7
8 9 10
- 样例输出：
Yes
No
No
代码（一）：
题解：
1、找到所在位置所在行，通过和每一行最后一个元素比较
2、找到列中元素位置
代码（二）、
题解：
1、二分查找第几行
2、二分查找第几列
代码（三）、
题解：
1、将二维数组转化成一维数组，进行二分查找
2、开数组注意是否爆出空间
代码（四）、
题解：
1、通过输入元素进行判断是否为所查找元素
小总结：
1、刚开始还是被输入给骗了，结果这种代码还能AC = =！
2、看来是九度OJ不想让我对自己的能力太伤心，给我放水了。
3、以上代码的思路其实是不对的。。。
4、假如题目真的像看上去那么容易，面试官也不会出这种题目吧，浪费TIME。。。
01，02，08，09
02，04，09，12
04，07，10，13
06，08，11，15
该矩阵的最小值m在左上角，最大值M在右下角。
从这样的一个矩阵中任意圈出一个子矩阵，也符合这个规律。
一个整数k，如果小于m或者大于M，则必然不在这个矩阵内。
将该矩阵分成上下两部分：
01，02，08，09
02，04，09，12
------------
04，07，10，13
06，08，11，15
如果一个整数k，大于上半部分右下角的值（这里是12），则k必然不在上半部分。
如果一个整数k，小于上半部分左上角的值（这里是04），则k必然不在下半部分。
将该矩阵分成左右两部分：
01，02 | 08，09
02，04 | 09，12
04，07 | 10，13
06，08 | 11，15
如果一个整数k，大于左半部分右下角的值（这里是08），则k必然不在左半部分。
如果一个整数k，小于右半部分左上角的值（这里是08），则k必然不在右半部分。
01：在最上面的一条边上，通过二分法查找k，找到就退出。否则，找到比k大的最小整数，将其所在及右边的列统统“切掉”。
02：在最右面的一条边上，通过二分法查找k，找到就退出。否则，找到比k小的最大整数，将其所在及上边的行统统“切掉”。
03：以上每一步中，“切”之前的矩阵大小如果为0，则失败退出；以上两步结束后，如果还没找到，则返回01，继续切。