I wrote some code to do linear interpolation over a huge number of values. Matlab is capable of running interpolation very fast, but my c++ code takes much longer. What can I do different to make the code run faster?

int nearestNeighbourIndex(std::vector<double>& x,double &value)
{
    double dist;
    int idx;
    int i;
    double newDist;
    idx = -1;
    dist = 999;//This is an absurdly large number meant to be replaced on
    //the first iteration of the for loop
    for ( i = 0; i < x.size(); i++ ) {
        newDist = std::abs(value - x.at(i));
        if ( newDist < dist ) {
            dist = newDist;
            idx = i;
        }
    }
    return idx;
}


std::vector<double> interpolate(std::vector<double> x,std::vector <double> v, std::vector<double>LinearSpaced){
    std::vector<double> v_new;
    double dx, dv, m, b;
    size_t x_max_idx = x.size() - 1;
    size_t x_new_size = LinearSpaced.size();

    v_new.reserve(x_new_size);

    for (size_t i = 0; i < x_new_size; ++i)
    {
        size_t idx = nearestNeighbourIndex(x, LinearSpaced[i]);
        if (x[idx] > LinearSpaced[i])
        {
            dx = idx > 0 ? (x[idx] - x[idx - 1]) : (x[idx + 1] - x[idx]);
            dv = idx > 0 ? (v[idx] - v[idx - 1]) : (v[idx + 1] - v[idx]);
        }
        else
        {
            dx = idx < x_max_idx ? (x[idx + 1] - x[idx]) : (x[idx] - x[idx - 1]);
            dv = idx < x_max_idx ? (v[idx + 1] - v[idx]) : (v[idx] - v[idx - 1]);
        }

        m = dv / dx;
        b = v[idx] - x[idx] * m;

        v_new.push_back(LinearSpaced[i] * m + b);
    }
    return v_new;
}

'''