二维数组行式二分搜索无法遍历全部行的问题排查

你的核心问题是二分搜索的边界变量start和end没有在每行遍历前重置：

• 你把start = 0和end = m-1写在for循环外面，第一行的二分搜索会修改这两个变量的值（比如搜索29时，第一行的二分过程会让end最终变成1）。
• 当进入第二行及以后的行时，start和end还是保持上一行结束后的状态，导致后续行的while(start<=end)条件可能直接不成立，二分搜索根本不会执行，自然找不到后续行里的元素。

修复后的代码 #

#include <iostream>
using namespace std;

//row-wise binary search.
int search2DArray(int matrix[][4], int n, int m, int key){
    for(int i=0; i<n; i++){
        // 每次处理新行时，重置二分搜索的边界
        int start = 0, end = m-1;
        while(start<=end){
            int mid = (start+end)/2;

            if(matrix[i][mid] == key){
                cout<<"FOUND\n";
                return 0;
            }else if(matrix[i][mid] < key){ 
                start = mid + 1;
            }else{
                end = mid - 1;
            }   
        }
    }
    cout<<"NOT FOUND\n";
    return -1;
}

int main(){
    int matrix[4][4] = {{10,20,30,40},
                        {15,25,35,45},
                        {27,29,37,48},
                        {32,33,39,50}};
    
    search2DArray(matrix, 4, 4, 29);
    
    return 0;
}

修复说明 #

把start和end的声明与初始化移到for循环内部，这样每处理一行时，都会重新设置当前行的二分搜索范围（从第0列到第m-1列），确保每行的二分搜索都是独立进行的，不会被上一行的搜索状态干扰。

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