c++arraysloops2d

Not able to iterate through all the rows in 2D array in Row-Wise Binary Search


Why my for loop is not iterating to the rows in 2D array?

#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;

}

I tried to apply for loop to iterate all the rows of 2D array but couldn't get past the first row and always printing NOT FOUND for any input for row > 0.


Solution

  • When you finish a row you are neglecting to reset start and end, so the next row begins with start and end in an exit condition and immediately exits.

    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;
    
    }
    

    We can improve on this function with some good ol' C++ Template magic:

    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;
    
    }
    

    This version would be called with something like

    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
    

    A side note: A great many common software problems are already solved in the C++ Standard Library. Using std::binary_search and generalizing the container into iterators with std::begin and std::end lets you reduce the body of the function to

    for (const auto & row : matrix) 
    {
        if (std::binary_search(std::cbegin(row), 
                               std::cend(row), 
                               key))
        {
            std::cout << "FOUND\n";
            return 0;
        }
    }
    std::cout << "NOT FOUND\n";
    return -1;
    

    and use it for arrays and any library container (though for most containers it wouldn't make sense. Why binary search a map?).