2.二维数组中的查找（python和java实现）

题目：在一个二维数组中，每一行都是按照从左到右递增的顺序排序，每一列都是安装从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中书否含有该整数。

算法思想：我们知道每一行都是递增排序的，每一列也是从上到下递增排序的，所以左上角的数是最小的，而右下角的数是最大的

1、选取右上角的数；

2,、判断比较右上角的数和传入的数值的大小，如果等于该参数的值，查找结束；

3、如果大于参数，则可以把这一列剔除；

4、如果小于参数，就剔除该数值所在的行

也就是说如果要查找的数字不在数组的右上角免责每一次艘在数组的查找范围中提出一行或者一列，这样每一步就可以缩小范围，知道找到要查找的数字，护照额查找范围为空

实现代码，

python版本：

# -*- coding:utf-8 -*- class Solution: def Find(self, target, array): n=len(array) flag='false' for i in range(n): if target in array[i]: flag='true' break return flag while True: try: S = Solution() L=list(eval(raw_input())) array=L[1] target=L[0] print(S.Find(target, array)) except: break

java版本：

思想：因为每一行和每一列都是递增顺序，可以从左下角或者右上角开始，例如从右上角开始，如果比右上角数据大，则行数加一，如果比他小，列数减一

public class Solution { public boolean Find(int target, int [][] array) { //boolean flag=false; int n=array[0].length-1; int i=0; while ((n>=0)&&(i<array.length)){ if (target>array[i][n]) { i++; }else if (target<array[i][n]){ n--; }else{ //flag=true; return true; } } //return flag; return false; } }

方法一：从右上角开始查找C/C++：

class Solution { public: bool Find(int target, vector<vector<int> > array) { bool found=false; int Rows = array.size(); int Cols = array[0].size(); if(Rows>0 && Cols>=0){ int r=0; int c=Cols-1; while(r<Rows && c>=0){ if(array[r][c]==target){ found=true; break; } else if(array[r][c]>target){ --c; } else ++r; } } return found; } };

方法二：从左下角开始查找C#：

class Solution { public bool Find(int target, int[][] array) { bool found=false; //从左下角开始查找 int rows=array.Length; int columns=array[0].Length; if(array!=null&&columns>0 && rows>=0){ int c=0; int r=rows-1; while(c<columns && r>=0){ if(array[r][c]==target){ found=true; break; } else if(array[r][c]<target){ ++c; } else --r; } } return found; } } 测试用例：

1、二维数组中包含查找的数字

2、不包含查找的数字

3、特殊输入测试（输入空指针）