Java矩阵二分搜索问题：for循环错误导致目标行未匹配

问题根源 #

你的代码中searchInSortedMatrix方法的逻辑存在缺陷：当前代码会找到第一个满足X >= 行首元素 && X <= 行尾元素的行，直接对该行执行二分搜索并返回结果。但你使用的矩阵中，行与行的数值范围存在重叠（比如第一行[10,40]和第三行[27,48]都包含目标值37），导致代码优先搜索第一行，而第一行并不存在37，最终错误返回0。

解决方案 #

方案1：修改遍历逻辑（最小改动）

保持原有的遍历+二分搜索结构，改为对所有满足范围条件的行逐一搜索，直到找到目标值或遍历完所有行：

public static int searchInSortedMatrix(int[][] mat, int X) {
    
    for (int i = 0; i < mat.length; i++) {
        // 检查目标值是否在当前行的范围内
        if(X >= mat[i][0] && X <= mat[i][mat[i].length - 1]) {
            int searchResult = binarySearch(mat[i], X);
            if(searchResult == 1) {
                return 1; // 找到目标，立即返回
            }
            // 未找到则继续检查下一行
        }
    }
    return 0; // 所有行均未找到目标
}

方案2：利用矩阵特性高效定位（更优）

由于矩阵每行、每列均递增，可以采用从右上角开始的搜索法，时间复杂度为O(n+m)（n为行数，m为列数），无需额外的二分搜索：

public static int searchInSortedMatrix(int[][] mat, int X) {
    int rows = mat.length;
    if (rows == 0) return 0;
    int cols = mat[0].length;
    
    // 从右上角元素开始搜索
    int currentRow = 0;
    int currentCol = cols - 1;
    
    while (currentRow < rows && currentCol >= 0) {
        if (mat[currentRow][currentCol] == X) {
            return 1; // 找到目标
        } else if (mat[currentRow][currentCol] > X) {
            currentCol--; // 目标值更小，向左移动
        } else {
            currentRow++; // 目标值更大，向下移动
        }
    }
    return 0; // 未找到目标
}

验证结果 #

修改后运行代码，目标值37会被正确定位到第三行（方案1），或通过右上角搜索直接找到（方案2），最终返回预期结果1。

内容的提问来源于stack exchange，提问作者Mohana Priya