Найти индекс ближайшего в отсортированном векторе

Question

Я написал процедуру C++, чтобы найти ближайший двойной элемент в отсортированном массиве. Есть ли способ ускорить работу?

Существует два филиала на основе значения boolean reversed, если reversed сортируется в порядке убывания.

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; 
       } 
      } 
     } 
    } 
} 

В этом случае, когда массив отсортирован, я не вижу способа сделать лучше. Итак, с профилированием я вижу, что сравнение в if (value <= x[i] && value > x[i + 1]) дорого.

EDIT

попытался с 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

Реализован этот помощник рутинную

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; 
    } 
} 

Answer 2

Вы можете использовать std::lower_bound найти элемент, равный или больше, чем требуется, а затем переместить итератор назад и проверить предшествующее значение тоже. Это будет использовать двоичный поиск и будет стоить O (log n), также это позволяет стандартные STL-компараторы и так далее.

Answer 3

Если вы на самом деле не вектор для использования с upper_bound() вам не нужно, чтобы построить один, как собирается быть O (п) операции. upper_bound() будет работать с массивом, который у вас есть. Вы можете использовать:

l_idx = std::upper_bound(x, x + size, value) - x - 1; 

Контрольный пример:

#include <iostream> 
#include <functional> 
#include <algorithm> 

int main() 
{ 
    const int size = 9; 
    int x[9] = {1,2,3,4,5,6,7,8,9}; 

    auto pos = std::upper_bound(x, x + size, 5) - x; 

    std::cout << "position: " << pos; 

    return 0; 
} 

Выход:

5 

В результате upper_bound() указывает нам на 6 (live example).