code to search an integer in a sorted matrix does not execute after taking input

Question

The following piece of code takes the input but does not execute or return any output.It takes a matrix and its size and an integer to be searched as input. I am failing to understand the issue here.

#include<iostream>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    int a[n][m];
    int t;
    cin >> t;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
        }
    }
    int r = 0, c = m - 1;
    bool found = false;
    while (r < n && c >= 0)
    {
        if (a[r][c] == t)
        {
            found = true;
        }
        else if (a[r][c] < t)
        {
            r++;
        }
        else
        {
            c--;
        }
    }
    if(found)
    {
        cout << "found";
    }
    else
    {
        cout << "not found";
    }
    return 0;
}

C++ doesn't have [variable-length arrays](https://en.wikipedia.org/wiki/Variable-length_array). Please get [some good C++ books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) and learn C++ properly rather than go to "competition" sites. — Some programmer dude, Apr 10 '21 at 05:26
`while (r < n && c >= 0)` loops and increments `r++;` each iteration that `a[r][c] < t`. That logic would seem to miss checking a lot of the elements. It looks like you want to search column-wise, but if the `a[r][c] < t` test fails, you skip checking the remaining rows in the column. In both cases, you never reset `r` or `c`. — David C. Rankin, Apr 10 '21 at 05:36
@DavidC.Rankin sorry i forgot to menton that the rows and columns are sorted in ascending order. So the brute force approach of checking each row and column linearly in not necessary. The search starts at the top right corner i.e. a[0][m-1] so if a[r][c]t, then t is not present in column c, hence c--. — Mangalam, Apr 10 '21 at 05:55
@Someprogrammerdude could you please help by telling how are these variable length arrays, as the length is taken input by the user. I didnot get it. Maybe i am missing something. — Mangalam, Apr 10 '21 at 06:01
@Mangalam The size of an array in C++ must be a compile-time-constant (except when using `new []` of course). `int a[n][m];` would only be legal C++ if `n` and `m` would have fixed values at compile time. But they don't, thus they are called "variable length array". You (and almost everyone who learns C++ from "competetive coding") are using this compiler specific extension without knowing how it works and getting screwed by it. [This question](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard) sums it up pretty well. — Lukas-T, Apr 10 '21 at 06:12
@Mangalam, if the answer satisfies your query please mark it so that others may know who have the same problem. Or if there is something still unclear let me know. — KL_KISNE_DEKHA_HAI, Apr 11 '21 at 12:18

KL_KISNE_DEKHA_HAI · Answer 1 · 2021-04-10T07:53:57.950

Writing break after the number is found gives what you want. You are not exiting the loop after a number has been found.

#include<iostream>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    int a[n][m];
    int t;
    cin >> t;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
        }
    }
    int r = 0, c = m - 1;
    bool found = false;
    while (r < n && c >= 0)
    {
        if (a[r][c] == t)
        {
            found = true;
            break;
         // ^^^^^^^
        }
        else if (a[r][c] < t)
        {
            r++;
        }
        else
        {
            c--;
        }
    }
    if(found)
    {
        cout << "found";
    }
    else
    {
        cout << "not found";
    }
    return 0;
}

UPDATE 1.0: Updated code considering comments of variable length array. Used vector in C++ to achieve the same purpose.

#include<iostream>
#include<vector>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    
    // Using vector of vectors instead of 2-D array
    vector< vector <int> > a(n);
    for(int i = 0; i < n; i++){
        a[i] = vector<int> (m);
    }
    
    int t;
    cin >> t;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
        }
    }
    int r = 0, c = m - 1;
    bool found = false;
    while (r < n && c >= 0)
    {
        if (a[r][c] == t)
        {
            found = true;
            break;
         // ^^^^^^^
        }
        else if (a[r][c] < t)
        {
            r++;
        }
        else
        {
            c--;
        }
    }
    if(found)
    {
        cout << "found";
    }
    else
    {
        cout << "not found";
    }
    return 0;
}

i have clearly mentioned adding a break after the number is found and that is what i have done also. After the found = true, added a break statement. With this change it runs bug free — KL_KISNE_DEKHA_HAI, Apr 10 '21 at 06:25
Just as you shouldn't repost basically the same question multiple times, you shouldn't repost the same answer. If you want to update an answer then *edit* it. And also please take some time to refresh [how to write good answers](https://stackoverflow.com/help/how-to-answer). — Some programmer dude, Apr 10 '21 at 06:25
Yeah was in a hurry so deleted my previous answer, but now i have mentioned everything please take a look — KL_KISNE_DEKHA_HAI, Apr 10 '21 at 06:27
Yes, after marking the line with a comment it becomes clear what you changed. Still, I consider `int a[n][m];` a bug, because it will fail horribly when `m` and `n` get too large. That is, because VLAs are a compiler specific extension and afaik are allocated on the stack. — Lukas-T, Apr 10 '21 at 07:45
Updated my answer @churill, please have a look now. You can also improve my answer if you want. — KL_KISNE_DEKHA_HAI, Apr 10 '21 at 07:54

code to search an integer in a sorted matrix does not execute after taking input

1 Answers1