Computing median of std::vector<double> causing segfault

Question

The following function is supposed to compute the median of a std::vector<double>.

double vecMed(vector<double>& vec) {

    vector<double> copyVec = vec;

    sort(copyVec.begin(), copyVec.end());

    if( copyVec.size()%2 == 0)
        return (copyVec[floor(static_cast<double>(copyVec.size())/2.0)] + copyVec[ceil(static_cast<double>(copyVec.size())/2.0)]) / 2.0;
    else
        return copyVec[copyVec.size()/2];
}

I'm getting a segfault on this line, sometimes:

return (copyVec[floor(static_cast<double>(copyVec.size())/2.0)] + copyVec[ceil(static_cast<double>(copyVec.size())/2.0)]) / 2.0;

Can anyone see a problem with this function?

The segfault might be due to memory corruption elsewhere that I'm unaware of, but I want to make sure I'm not making a subtle or careless mistake in the above code before I explore that possibility.

---

GDB says:

Program received signal SIGSEGV, Segmentation fault.
0x0000000000428ab6 in vecMed (this=0x7fffffffd1b0, vec=...) at ../globals.cpp:834
834         return (copyVec[floor(static_cast<double>(copyVec.size())/2.0)] + copyVec[ceil(static_cast<double>(copyVec.size())/2.0)]) / 2.0;
(gdb) bt
#0  0x0000000000428ab6 in vecMed (this=0x7fffffffd1b0, vec=...) at ../globals.cpp:834

Answer 1

So much errors in the code! I guess you want:

#include <algorithm>
#include <vector>

double vecMed(std::vector<double> vec) {
    if(vec.empty()) return 0;
    else {
        std::sort(vec.begin(), vec.end());
        if(vec.size() % 2 == 0)
                return (vec[vec.size()/2 - 1] + vec[vec.size()/2]) / 2;
        else
                return vec[vec.size()/2];
    }
}

Answer 2

First off, if the initial vector is empty, what you're doing is not safe.

Secondly, your logic isn't right in the even case. If copyVec.size() % 2 == 0, it's even, so static_cast<double>(copyVec.size())/2.0 is an integer. So both the floor and ceil are the same thing, so that's probably not what you want to do. Prefer something like:

const int mid = copyVec.size() / 2;
if (copyVec.size() % 2 == 0) {
    return 0.5 * (copyVec[mid] + copyVec[mid+1]); // safe unless size == 0
}
else {
    return copyVec[mid]; // e.g. if size == 3, return copyVec[1]
}

Answer 3

You don't need floor of ceil, you can do this far more efficiently using integer arithmetic:

return (copyVec[copyVec.size()/2] + copyVec[(copyVec.size() + 1)/2]) / 2.0;

Now this code will do the same as yours but it is easier to read and understand. Start by trying out some simple cases and some edge cases. In this case you may note that your code does not run correctly for an empty array.

Lets assume you don't see anything suspicious in the code you investigate your best option is to use a debugger. Sometimes using valgrind would also help if you have a stack corruption.

Also you may want to consider using std::nth_element for finding the median of a vector.