# 原创
： 1.剑指Offer编程题之二维数组中的查找
# 1.剑指Offer编程题之二维数组中的查找
**题目描述:**
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数.
**解题思路1：**
- 从左下角元素开始往上查找，右边元素比这个元素大，上边元素比这个元素小，于是，target比这个元素小就往上找，比这个元素大就往右找.如果出现边界，则查找失败.
C/C++
```
class Solution{
public:
//二维向量这里最外的<>要有空格。否则在比较旧的编译器下无法通过
bool Find(int target, vector< vector<int> >array){
if(array.empty()) return false;
int rows = array.size();
int cols = array[0].size();
int i=rows-1,j=0; //左下标元素坐标
while(i>=0&&j<cols){
if(target<array[i][j]) --i;
else if(target>array[i][j]) ++j;
else return true;
}
return false;
}
};
```
Python2
```
class Solution:
def Find(self,target,array):
rows = len(array)
cols = len(array[0])
i = rows-1
j = 0
while j<cols and i>=0:
if target<array[i][j]:
i -= 1
elif target>array[i][j]:
j += 1
else:
return True
return False
```
Java
```
public class Solution{
public boolean Find(int target, int [][] array){
int rows = array.length;
int cols = array[0].length;
int i = rows-1,j=0;
while(i>=0&&j<cols){
if(target<array[i][j])--i;
else if(target>array[i][j])++j;
else return true;
}
return false;
}
}
```
**解题思路2：**
从右上角开始查找，左边元素比这个元素小，下边元素比这个元素大，于是target比这个元素大，则往下找，比这个元素小则往左找，出现边界查找失败.
C/C++
```
class Solution{
public:
//二维向量这里最外的<>要有空格。否则在比较旧的编译器下无法通过
bool Find(int target, vector< vector<int> >array){
if(array.empty())return false;
int rows = array.size();
int cols = array[0].size();
int i=0,j=cols-1;
while(i<=rows-1&&j>=0){
if (target<array[i][j])--j;
else if(target>array[i][j])++i;
else return true;
}
return false;
}
};
```
Python2
```
class Solution:
def Find(self,target,array):
rows = len(array)
cols = len(array[0])
i = 0
j = cols-1
while i<rows-1 and j>=0:
if target<array[i][j]:
j -= 1
elif target>array[i][j]:
i += 1
else:
return True
return False
```
Java
```
public class Solution{
public boolean Find(int target, int [][] array){
int rows = array.length;
int cols = array[0].length;
int i=0,j=cols-1;
while(i<=rows-1&&j>=0){
if(target<array[i][j])--j;
else if(target>array[i][j])++i;
else return true;
}
return false;
}
}
```
**解题思路3：**
把每一行看成是一个有序递增数组，利用二分法查找，通过遍历每一行得到答案，时间复杂度nlogn.
C/C++
```
class Solution{
public:
bool Find(int target,vector< vector<int> >array){
if(array.empty()) return false;
int length=array.size();
for(int i=0;i<length;++i){
int low = 0;
int high = array[i].size()-1;
while(low<=high){
int mid = (low+high)/2;
if(target>array[i][mid]) low=mid+1;
else if(target<array[i][mid]) high=mid-1;
else return true;
}
}
return false;
}
};
```
Python2
```
class Solution:
def Find(self,target,array):
length=len(array)
for i in range(length):
low = 0
high = len(array[i])-1
while low<=high:
mid = (low+high)/2
if target>array[i][mid]:
low = mid + 1
elif target<array[i][mid]:
high = mid-1
else:
return True
return False
```
Jave
```
public class Solution{
public boolean Find(int target, int [][] array){
int length=array.length;
for(int i=0;i<length;++i){
int low = 0;
int high = array[i].length-1;
while(low<=high){
int mid = (low+high)/2;
if(target>array[i][mid])low=mid+1;
else if(target<array[i][mid])high=mid-1;
else return true;
}
}
return false;
}
}
```
>
本实例均通过牛客网在线编译测试。