剑指 Offer 04. 二维数组中的查找

剑指 Offer 04. 二维数组中的查找 - 力扣（Leetcode）

在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

例子：

[[1,  4,  7, 11, 15],[2,  5,  8, 12, 19],[3,  6,  9, 16, 22],[10, 13, 14, 17, 24],[18, 21, 23, 26, 30]
]
//给定 target = 5，返回 true。
//给定 target = 20，返回 false。

每一行都按照从左到右 非递减 的顺序排序也就是顺序排序却不是递减，那么就是递增

每一列都按照从上到下 非递减 的顺序排序也就是顺序排序却不是递减，那么就是递增观察代码，我们会发现每个元素的下右都是大于他的，而上左都是小于他的

 那么我们开辟思路我们从整个二维数组四边形的

 寻找方式为对角线查找流。

这里的开始方向必须是右上到左下。因为如果是左上或者右下开始，数据的两边都是大于或小于原来的值就没办法查找了

 但是如果是左下或者右上开始，就可以与target比较大小后移动了

这里我们来执行查找流程（右上开始）target==5

15比5大向左一位查找

 11比5大向左一位查找

7比5大向左一位查找

4比5小向下一位查找

 找到了！！返回ture

现在target为20开始查找，

15比20小，向下一位查找

19比20小，向下一位查找

 22比20大，向左一位查找

16比20小，向下一位查找

17比20小，向下一位查找

  26比20大，向左一位查找

 向左一直比20大，直到18

 18比20小向下超出范围，退出查找，返回false

 这就是我们的查找原理，看源代码。

bool findNumberIn2DArray(int** matrix, int matrixSize, int* matrixColSize, int target)
{if(matrixSize==0||(*matrixColSize)==0){return false;}int col = *matrixColSize - 1;int row=0;while(row<matrixSize&&col>=0){if(matrix[row][col]>target){col--;}else if(matrix[row][col]<target){row++;}else{return true;}}return false;
}