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

Question

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.

Answer 1

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?).