-1

I was solving a question which required me to find the upper bound of an value in 1st array in 2nd array,so i used bianry search. now even though the expected output and my code's output match perfectly, the compiler is throwing an error.

here is my code -

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int n,m;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    cin>>m;
    vector<int>b(m);
    for(int i=0;i<m;i++){
        cin>>b[i];
    }
    
    sort(a.begin(),a.end());
    vector<int>res(m);
    for(int i=0;i<n;i++)
    {
        int l=0,r=n-1;
        while(l<=r){
            int m=(l+r)/2;
            if(a[m] <= b[i])  l=m+1;
            else    r=m-1;
        }
        
        res[i] = r<0? 0 : r+1;
    }
    
    for(int x=0;x<m;x++){
        cout<<res[x]<<endl;
    }
    return 0;
}

input - 7 23 4 2 12 18 20 16 4 13 22 29 1

expected output - 3 6 7 0

my output - 3 6 7 0

here is the complier message and the error.

compiler message -Abort Called

Error (stderr) -

munmap_chunk(): invalid pointer
Reading symbols from Solution...done.
[New LWP 1616800]
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
Core was generated by `./Solution'.
Program terminated with signal SIGABRT, Aborted.#0  __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
To enable execution of this file add
    add-auto-load-safe-path /usr/local/lib64/libstdc++.so.6.0.25-gdb.py
line to your configuration file "//.gdbinit".
To completely disable this security protection add
    set auto-load safe-path /
line to your configuration file "//.gdbinit".
For more information about this security protection see the
"Auto-loading safe path" section in the GDB manual.  E.g., run from the shell:
    info "(gdb)Auto-loading safe path"
Abhi
  • 1
  • 1
  • You'll be glad to hear you don't need anyone's help to figure this out, just a tool you already have: your debugger! This is exactly what a debugger is for. It [runs your program, one line at a time, and shows you what's happening](https://stackoverflow.com/questions/25385173/), this is something that's every C++ developer must know how to do. With your debugger's help you'll able to quickly find all problems in this and all future programs you write, without having to ask anyone for help. Have you tried using your debugger, already? If not, why not? What did your debugger show you? – Sam Varshavchik Mar 21 '22 at 16:10
  • 3
    Any reason to not use [std::lower_bound](https://en.cppreference.com/w/cpp/algorithm/lower_bound) and [std::upper_bound](https://en.cppreference.com/w/cpp/algorithm/upper_bound)? Given that, with your current code, change this: `if(a[m] <= b[i])` to this: `if(a.at(m) <= b.at(i))` and report what you now see as an error. Even better, if that now gives you a `std::out_of_range` exception, use the debugger to figure out why you are going out of range (as suggested by the earlier comment). – PaulMcKenzie Mar 21 '22 at 16:10

1 Answers1

0

The problem with your code is that you are accessing elements of a vector that may not exist.

You have defined res as a vector of size m. However, in the for loop just after its definition, you are using n as the upper bound, which at some point further down, is used in res[i] = r<0? 0 : r+1;. In your example test, n is 7 and m is 4. Therefore, when i == 6, res[i] is invalid.

moriaz
  • 96
  • 6