题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例1
输入
7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值
true
思路
(旨在拓宽思路，并非标答)
这道题目里涉及的矩阵名为杨氏矩阵，杨氏矩阵的查找是非常经典的问题。
方法一：暴力
剑指offer很多题都存在数据弱的问题，下表是暴力花的时间。
| 解决问题 | 提交时间 | 状态 | 运行时间 | 占用内存 | 使用语言 |
|---|---|---|---|---|---|
| 二维数组中的查找 | 2020-09-18 | 答案正确 | 8 ms | 1528K | C++ |
方法二：二分+递归
1. 二分知识点的复习
在一维数组里查找某个数，如果数组有序，那么可以采用二分的方法：
#include <iostream>
using namespace std;
int BiSearch(int arr[],int target,int size){
int l=0,r=size-1;
while(l<=r){
int mid = (l+r)/2;
if(arr[mid]==target) return mid;
else if(arr[mid]>target) r = mid-1;
else l = mid+1;
}
return -1;
}
int main(){
int arr[10] = {0,1,2,3,4,5,6,7,8,9};
int target = 2;
cout<<BiSearch(arr,target,10)<<endl;
return 0;
}
2. 二分能否运用到这道题里面
虽然二维数组从上到下，从左到右都是有序的，但是当一个pos确认比tar大的时候，我们只能排除它右下角的数据，显然不能直接使用二分查找。在借鉴了其他的思路后，我思考着能否将二分也套用进去。
原思路
原解题思路的具体过程可以参照牛客的官方题解。
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
this->height = int(array.size());
if(height==0) return false;
this->width = int(array[0].size());
int i=height-1,j=0;
while(i>=0&&j<width){
if(array[i][j]==target) return true;
else if(array[i][j]>target) i--;
else j++;
}
return false;
}
private:
int height;
int width;
};
二分优化版
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int height = int(array.size());
if(height==0) return false;
int width = int(array[0].size());
int li=height-1,ri=0,lj=0,rj=width-1;
int i=li,j=lj;
while(i>=0&&j<width){
if(array[i][j]==target) return true;
else if(array[i][j]>target){
while(li>=ri){
int mid = (li+ri)/2;
if(array[mid][j]==target) return true;
else if(array[mid][j]<target) ri = mid+1;
else li = mid-1;
}
i = li;
ri = 0;
}
else{
while(lj<=rj){
int mid = (lj+rj)/2;
if(array[i][mid]==target) return true;
else if(array[i][mid]>target) rj = mid-1;
else lj = mid+1;
}
j = lj;
rj = width-1;
}
}
return false;
}
};
不过这样的写法在牛客上和原思路花了一样的时间，不知道是不是我的写法有问题，欢迎探讨。
