Найти индекс ближайшего в отсортированном векторе
Я написал подпрограмму C ++, чтобы найти ближайший двойной элемент в отсортированном массиве. Есть ли способ ускорить?
Есть две ветви, основанные на значении логического 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]) дорогой.
РЕДАКТИРОВАТЬ
попробовал с 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;
Решение
Ты можешь использовать станд :: lower_bound найти элемент, равный или больший, чем запрашиваемый, а затем переместить итератор назад и также проверить предыдущее значение. Это будет использовать двоичный поиск и будет стоить O (log n), также это позволяет использовать стандартные компараторы STL и так далее.
Другие решения
Если у вас нет вектора для использования с upper_bound() вам не нужно создавать его, так как это будет операция O (n). 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 (живой пример).
Реализована эта вспомогательная процедура
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;
}
}