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