剑指offer(c++)-02.二维数组中的查找
2.二维数组中的查找
题目：
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
如：target = 7,
二维数组如下：
[
[1,2, 8, 9 ],
[2,4, 9, 12],
[4,7,10,13],
[6,8,11,15]
]
二分值法
思想：（拐点为二分值）
- 观察数字的规律，第一行与最后一列构成递增数列（1,2,8,9,12,13,15），第二行与倒数第二列构成递增数列（2,4,9,10,11）…因此可利用拐点（加粗数字）作为判断条件
- 当target = 拐点数字，则相等，输出true
- 当target > 拐点数字（说明target在更大位置，即列不变行增加），则行增加，即row++
- 当target < 拐点数字（说明target在更小位置，即列缩小继续查找），则列减少，即col–
- 遍历未找出，输出false
class Solution {
// target: 需要查找的值
// array: 输入数组
public:
bool Find(int target, vector<vector<int> > array) {
if(array.empty() || array[0].empty()) return false;
int row = 0,col = array[0].size() - 1;
while(row <= array.size() -1 && col >= 0){
if(array[row][col] == target) return true;
if(array[row][col] > target) col--;
else row++;
}
return false;
}
};