如何正确实现二分查找？求助解决LeetCode 74题《搜索二维矩阵》的代码问题

兄弟，我帮你看看代码里的问题哈，你的思路是对的——先定位目标所在的行，再在该行内二分查找目标，但细节上没处理好，导致出现错误答案或者超时的情况，咱们一步步捋清楚：

你当前代码的核心问题 #

1. 找行的逻辑漏洞
   你现在的行查找逻辑只对比了target和当前行的第一个元素，但忽略了target可能就在当前行中间的情况。比如，假设matrix[mid][0] < target < matrix[mid][-1]，这时候你的代码会执行left = mid + 1，继续往后面的行找，最后要么找不到正确的行，要么循环结束后index还是初始值0，导致后续访问错误的行。

2. 找列时的return错误
   在第二个二分循环里，当找到target == matrix[index][mid]时，你只写了True，但没有return语句，程序会继续执行循环，最后走到末尾的return False，这就导致明明找到目标了却返回错误结果！

3. 边界情况未处理
   比如target比矩阵所有元素都大/小，或者矩阵为空的情况，你的代码会直接访问matrix[index]，可能引发索引越界或者错误判断。

修正后的代码及解释 #

我给你调整了代码，同时保留你“先找行再找列”的思路，修复了上述问题：

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # 先处理空矩阵的特殊情况
        if not matrix or not matrix[0]:
            return False
        
        rows = len(matrix)
        cols = len(matrix[0])
        
        # 第一步：找到target所在的行
        left, right = 0, rows - 1
        target_row = 0
        while left <= right:
            mid = (left + right) // 2
            # 如果target在当前行的范围内，直接确定这一行
            if matrix[mid][0] <= target <= matrix[mid][-1]:
                target_row = mid
                break
            # 如果target比当前行第一个元素小，去左边找
            elif target < matrix[mid][0]:
                right = mid - 1
            # 如果target比当前行最后一个元素大，去右边找
            else:
                left = mid + 1
        else:
            # 循环正常结束，说明没有找到符合条件的行，直接返回False
            return False
        
        # 第二步：在目标行内二分查找target
        left_col, right_col = 0, cols - 1
        while left_col <= right_col:
            mid_col = (left_col + right_col) // 2
            if matrix[target_row][mid_col] == target:
                return True
            elif matrix[target_row][mid_col] < target:
                left_col = mid_col + 1
            else:
                right_col = mid_col - 1
        
        # 行内没找到，返回False
        return False

关键细节说明 #

• 行查找的优化：每次判断target是否在当前mid行的范围内（matrix[mid][0] <= target <= matrix[mid][-1]），是的话直接锁定该行，避免无效的循环移动。
• 循环的else分支：当行查找的while循环正常结束（没有触发break），说明不存在包含target的行，直接返回False，不用再进行列查找。
• 正确的return时机：在列查找中，一旦找到target就立即return True，确保结果正确；循环结束后返回False，表示行内没有找到目标。

这样调整后，代码就能满足O(log(m*n))的时间复杂度，同时处理所有边界情况啦。

备注：内容来源于stack exchange，提问作者user430243