摘要：
本文将围绕LeetCode上的经典题目“二分查找二维数组（行列有序矩阵）”展开，深入探讨二分查找算法在解决行列有序矩阵查找问题中的应用。通过分析题目背景、解题思路、代码实现以及性能优化等方面，帮助读者全面理解二分查找在二维有序矩阵中的应用。
一、题目背景
在LeetCode中，有一个经典的题目叫做“二分查找二维数组（行列有序矩阵）”。题目描述如下：
给定一个按行和列都升序排列的二维数组 matrix，编写一个函数，找出给定目标值 target 是否存在于该矩阵中。如果存在，则返回其索引；如果不存在，则返回 [-1, -1]。
示例：
matrix = [
[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
输出：`[1, 2]`
二、解题思路
由于矩阵是按行和列都升序排列的，我们可以利用二分查找的思想来解决这个问题。具体思路如下：
1. 将二维数组转换为一维数组，并计算转换后的索引。
2. 对一维数组进行二分查找。
3. 如果找到目标值，则将一维索引转换回二维索引。
4. 如果未找到目标值，则返回 [-1, -1]。
三、代码实现
下面是使用Python实现的代码示例：
python
def searchMatrix(matrix, target):
if not matrix or not matrix[0]:
return [-1, -1]
rows, cols = len(matrix), len(matrix[0])
left, right = 0, rows cols - 1
while left <= right:
mid = (left + right) // 2
mid_val = matrix[mid // cols][mid % cols]
if mid_val == target:
return [mid // cols, mid % cols]
elif mid_val < target:
left = mid + 1
else:
right = mid - 1
return [-1, -1]
测试代码
matrix = [
[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
print(searchMatrix(matrix, target)) 输出：[1, 2]
四、性能优化
在上述代码中，我们将二维数组转换为一维数组，这可能会增加额外的内存消耗。为了优化性能，我们可以直接在原二维数组上进行二分查找，避免转换。
下面是优化后的代码：
python
def searchMatrixOptimized(matrix, target):
if not matrix or not matrix[0]:
return [-1, -1]
rows, cols = len(matrix), len(matrix[0])
left, right = 0, rows cols - 1
while left <= right:
mid = (left + right) // 2
mid_val = matrix[mid // cols][mid % cols]
if mid_val == target:
return [mid // cols, mid % cols]
elif mid_val < target:
left = mid + 1
else:
right = mid - 1
return [-1, -1]
测试代码
matrix = [
[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
print(searchMatrixOptimized(matrix, target)) 输出：[1, 2]
五、总结
本文通过分析LeetCode上的“二分查找二维数组（行列有序矩阵）”题目，详细介绍了二分查找算法在解决行列有序矩阵查找问题中的应用。通过代码实现和性能优化，帮助读者更好地理解二分查找算法在二维有序矩阵中的应用。在实际编程中，我们可以根据具体问题选择合适的算法和数据结构，以达到最优的性能。
Comments NOTHING