剑指offer_01_二维数组中的查找
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解题思路
该二维数组中的一个数，他左边的数都比他小，下边的数都比他大。因此，可以从右上角开始查找，根据target与数组中元素的关系来缩小查找区间，当前元素的查找区间为该元素左下角的所有元素。
假设数组为
array[4][4]={1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16};
target=14;
那么数组左上角元素为array[0][3]=4，查找过程如下图所示
- 将array[0][3]与target比较，4小于14，则行标 r增加1
- 将array[1][3]与target比较，8小于14，则行标 r再增加1
- 将array[2][3]与target比较，12小于14，则行标 r继续增加1
- 将array[3][3]与target比较，16大于14，则列标 c减小1
- 将array[3][2]与target比较，15大于14，则行标 c继续减1
- 将array[3][1]与target比较，14等于14，说明已在array中找到target，返回true
- 如果从数组右上角查找到左下角都没有找到target，则说明数组中不存在要查找的target,返回false
Java代码实现如下
public static boolean Find(int target, int[][] array) {
if (array == null)
return false;
// 判断输入是否为空，如果为空则直接返回false
int row = array.length, cols = array[0].length;
// 数组行数为row，列数为cols
int r = 0, c = cols - 1;
// c=cols-1,列标最大值为列数减1
while (r <= row - 1 && c >= 0) {
// 当满足行标小于行数减1 ，并且列标大于等于0的条件时，进行查找
if (target == array[r][c])
return true;
// 如果该元素与target相等，返回true
else if (target > array[r][c])
r++;
// 如果target大于数组元素，则将其和该元素下方元素进行比较
else
c--;
// 如果target小于数组元素，则将其和该元素左边元素进行比较
}
return false;
// 如果没有找到，返回false
}测试结果如下：
