代码之家 › 专栏 › 技术社区 › Himanshu

无法在逐行二进制搜索中迭代2D数组中的所有行

2d loops arrays c++

Himanshu · 技术社区 · 5 月前

为什么我的for循环不迭代到2D数组中的行?

#include <iostream>
using namespace std;

//row-wise binary search.

int search2DArray(int matrix[][4], int n, int m, int key){
int start = 0, end = m-1;

    for(int i=0; i<n; i++){
    
        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;

}

我试图应用循环来迭代2D数组的所有行,但无法通过第一行,并且总是为行>的任何输入打印NOT FOUND;0.

1 回复 | 直到 5 月前

user4581301 5 月前

当你完成一行时,你忽略了重置 start 和 end ,所以下一行以 开始 和 结束 处于退出状态并立即退出。

int search2DArray(int matrix[][4], int n, int m, int key){
//    int start = 0, end = m-1; <<-- move this line 

    for(int i=0; i<n; i++){
        int start = 0, end = m-1; // <<-- to here
        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;

}

我们可以用一些好的C++模板魔法来改进这个函数:

template<size_t N, size_t M> // template deduction eliminates need for 
                             // m and n as parameters and arguments.
                             // code you don't have to write has no bugs.  
int search2DArray(int (&matrix)[N][M], int key)
{

    for (const auto & row : matrix) //range-based for loop allows easy 
                                    // processing of each row as a row
    {
        size_t start = 0; // split into two lines to make it harder to screw up.
        size_t end = M - 1; // using size_t because it can handle any array you 
                            // can give it.

        while (start <= end) // rest is pretty much the same
        {
            size_t mid = (start + end) / 2;

            if (row[mid] == key) // since we operate on rows we no longer 
                                 // care about the outer dimension
            {
                cout << "FOUND\n";
                return 0;
            }
            else if (row[mid] < key)
            {
                start = mid + 1;
            }
            else
            {
                end = mid - 1;
            }
        }

    }
    cout << "NOT FOUND\n";
    return -1;

}

此版本的调用方式如下

int matrix[][4] = // compiler figures out the outer dimension
{                 // I don't have a good way to infer the inner dimension 
                  // without getting weirder than this problem requires.
    { 10, 20, 30, 40 },
    { 15, 25, 35, 45 },
    { 27, 29, 37, 48 },
    { 32, 33, 39, 50 } 
};

search2DArray(matrix, 29); // compiler figures out the template arguments 
                           // from the array