第 4 题：二维数组中的查找
同 LeetCode 第 240 题，LeetCode 传送门：搜索二维矩阵 II，AcWing：二维数组中的查找，牛客网传送门：二维数组中的查找。
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
样例：
输入数组：
[ [1,2,8,9]， [2,4,9,12]， [4,7,10,13]， [6,8,11,15] ]如果输入查找数值为 7，则返回 true，
如果输入查找数值为 5 ，则返回 false。
分析：有点像 LeetCode 上岛屿的问题，特别之处：从右上角开始找，或者从左下角开始找，为什么不能选左上或者右下开始，因为不能缩小查找范围。首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数组，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。
《剑指 Offer （第 2 版）》第 4 题：二维数组中的查找-1
Python 代码：从右上角开始找，一个一个地找。小了向下面走，大了向左边走
class Solution(object):
def searchArray(self, array, target):
rows = len(array)
if rows == 0:
return False
cols = len(array[0])
if rows > 0 and cols > 0:
row = 0
col = cols - 1
# 注意：在横纵坐标都有意义的时候，才可以搜索，因此用 and
while row < rows and col >= 0:
if target == array[row][col]:
return True
elif target < array[row][col]:
# [4, 5, 6, 12, 13] 找 7
col -= 1
else:
# [7]
# [8]
# [12] 找 9
row += 1
# 全部走完都找不到，就说明没有
return False
说明：其实不管是每行还是每列，都是有序数组，所以可以使用二分法。我写了个二分法，只是作为练习。但是二分法不能保证一次写对，所以不建议在面试的时候写。
- 正确的搜索起点是从左下角或者右上角开始搜索，这是因为：
从下到上，数字越来越小；
从左到右，数字越来越大。 - 注意指针没有必要回退，这一点，在下面的代码注释中做了强调。
Java 代码：
public class Solution {
public boolean Find(int target, int[][] array) {
int row = array.length;
if (row == 0) {
return false;
}
int col = array[0].length;
// 从左下角开始搜索，先从左到右，再从下到上
int i = row - 1;
int j = 0;
while (i >= 0) {
while (j < col && array[i][j] < target) {
j++;
}
if (j < col && array[i][j] == target) {
return true;
}
i--;
}
return false;
}
public static void main(String[] args) {
int[][] matrix = new int[][]{
{1, 2, 8, 9},
{2, 4, 9, 12},
{4, 7, 10, 13},
{6, 8, 11, 15}
};
Solution solution = new Solution();
boolean find = solution.Find(16, matrix);
System.out.println(find);
}
}
Python 代码：（了解即可）
# 4、二维数组中的查找
class Solution(object):
# 二分法查找规律
# 1、从右到左，找第 1 个小于或者等于 target 的数
# 2、从上到下，找第 1 个大于或者等于 target 的数
def searchArray(self, array, target):
"""
:type array: List[List[int]]
:type target: int
:rtype: bool
"""
rows = len(array)
if rows == 0:
return False
cols = len(array[0])
col = cols - 1
row = 0
while row < rows and col >= 0:
# print('row', row, 'col', col, array[row][0])
# 1、从右到左，找第 1 个小于或者等于 target 的数
if col == 0 and array[row][0] > target:
return False
l = 0
r = col
while l < r:
mid = l + (r - l + 1) // 2
if array[row][mid] <= target:
l = mid
else:
assert array[row][mid] > target
r = mid - 1
col = l
# 2、从上到下，找第 1 个大于或者等于 target 的数
if row == rows - 1 and array[rows - 1][col] < target:
return False
l = row
r = rows - 1
while l < r:
mid = l + (r - l) // 2
if array[mid][col] >= target:
r = mid
else:
assert array[mid][col] < target
l = mid + 1
row = l
if array[row][col] == target:
return True
return False
if __name__ == '__main__':
array = [[1, 2, 8, 9],
[2, 4, 9, 12],
[4, 7, 10, 13],
[6, 8, 11, 15]]
target = 16
solution = Solution()
result = solution.searchArray(array, target)
print(result)
LeetCode 第 74 题：搜索二维矩阵
传送门：搜索二维矩阵。
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 输出: true示例 2:
输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 输出: false
Python 代码1：“标准的”二分法
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
m = len(matrix)
if m == 0:
return False
n = len(matrix[0])
if n == 0:
return False
left = 0
# 这里一定要记得减 1
right = m * n - 1
while left <= right:
mid = left + (right - left) // 2
# 定位到矩阵中
num = matrix[mid // n][mid % n]
if num == target:
return True
elif num < target:
left = mid + 1
else:
right = mid - 1
return False
Python 代码2：“神奇的”二分法模板
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
m = len(matrix)
if m == 0:
return False
n = len(matrix[0])
# [[]] 针对这种情况，要特判
if n == 0:
return False
l = 0
r = m * n - 1
while l < r:
mid = l + (r - l) // 2
if matrix[mid // n][mid % n] < target:
l = mid + 1
else:
r = mid
# 这个模板在退出循环的时候 l == r 成立，但是有可能存在不满足条件的时候
# 所以要单独判断
return matrix[l // n][l % n] == target
