Find index of nearest in sorted vector

Question

I wrote a C++ routine to find nearest double element in sorted array. Is there a way to speed up?

There are two branches based on the value of boolean reversed, if reversed it is sorted in the decreasing order.

 void findNearestNeighbourIndex_new(real_T value, real_T* x, int_T x_size, int_T& l_idx)
{
    l_idx = -1;

    bool reversed= (x[1] - x[0] < 0);

    if ((!reversed&& value <= x[0]) 
                  || (reversed&& value >= x[0])){ 
        // Value is before first position in x
        l_idx = 0;
    }
    else if ((!reversed&& value >= x[x_size - 1]) 
                    || (reversed&& value <= x[x_size - 1])){ 
        // Value is after last position in x
        l_idx = x_size - 2;
    }
    else // All other cases
    {
        if (reversed)
        {
            for (int i = 0; i < x_size - 1; ++i)
            {
                if (value <= x[i] && value > x[i + 1])
                {
                    l_idx = i;
                    break;
                }
            }
        }
        else{
            for (int i = 0; i < x_size - 1; ++i)  
            {
                if (value >= x[i] && value < x[i + 1])
                {
                    l_idx = i;
                    break;
                }
            }
        }   
    }
}

In this very case where array is sorted, I do not see a way to do better. So, with profiling i see that the comparison in if (value <= x[i] && value > x[i + 1]) is expensive.

EDIT

tried with lower_bound()

std::vector<real_T> x_vec(x, x + x_size);

l_idx = std::upper_bound(x_vec.begin(), x_vec.end(), value) - x_vec.begin() - 1;

Answer 1

Implemented this helper routine

void findNearestNeighbourIndex_bin_search_new(real_T value, real_T* x,  
              int_T start, int_T stop, int_T& l_idx)
{
    int_T mid = ( stop - start ) / 2;

    if (value >= x[mid+1])
    {
        findNearestNeighbourIndex_bin_search_new(value, x, mid + 1, stop, l_idx);
    }
    else if (value < x[mid])
    {
        findNearestNeighbourIndex_bin_search_new(value, x, start, mid, l_idx);
    }
    else
    {
        l_idx = mid;
        return;
    }
}