我有一个已排序的C++双精度值数组。是否有一个STL函数可以返回到给定双精度值最近的值在数组中的索引?
例如,给定以下数组:
double myarray[5] = { 1.0, 1.2, 1.4. 1.5, 1.9 };
函数调用
search(myarray, 1.6);
应该返回
3
,即最接近 1.6 的元素的索引,而不是返回 -1
(或其他某个标志值),表示值 1.6 未被找到。我有一个已排序的C++双精度值数组。是否有一个STL函数可以返回到给定双精度值最近的值在数组中的索引?
例如,给定以下数组:
double myarray[5] = { 1.0, 1.2, 1.4. 1.5, 1.9 };
search(myarray, 1.6);
3
,即最接近 1.6 的元素的索引,而不是返回 -1
(或其他某个标志值),表示值 1.6 未被找到。也许你可以尝试使用 std::lower_bound
和 std::upper_bound
。
以下是使用 std::lower_bound
的通用解决方案:
template <typename BidirectionalIterator, typename T>
BidirectionalIterator getClosest(BidirectionalIterator first,
BidirectionalIterator last,
const T & value)
{
BidirectionalIterator before = std::lower_bound(first, last, value);
if (before == first) return first;
if (before == last) return --last; // iterator must be bidirectional
BidirectionalIterator after = before;
--before;
return (*after - value) < (value - *before) ? after : before;
}
template <typename BidirectionalIterator, typename T>
std::size_t getClosestIndex(BidirectionalIterator first,
BidirectionalIterator last,
const T & value)
{
return std::distance(first, getClosest(first, last, value));
}
现在你最终得到了这样的代码:
const int ARRAY_LENGTH = 5;
double myarray[ARRAY_LENGTH] = { 1.0, 1.2, 1.4. 1.5, 1.9 };
int getPositionOfLevel(double level)
{
return getClosestIndex(myarray, myarray + ARRAY_LENGTH, level);
}
这将会得到以下结果:
level | index
0.1 | 0
1.4 | 2
1.6 | 3
1.8 | 4
2.0 | 4
这个数组是否保证是按升序排列的?如果是,可以尝试使用std::lower_bound
。
#include <algorithm>
#include <cmath>
const int ARRAY_LENGTH = 5;
double myarray[ARRAY_LENGTH] = { 1.0, 1.2, 1.4, 1.5, 1.9 };
struct CompareDistanceFromLevel
{
CompareDistanceFromLevel(double cLevel) : level(cLevel) {}
bool operator()(double lhs, double rhs)
{
return std::abs(level - lhs) < std::abs(level - rhs);
}
private:
double level;
};
size_t getPositionOfLevel(double level)
{
double *result;
result = std::min_element(myarray, myarray+ARRAY_LENGTH, CompareDistanceFromLevel(level));
return (result-myarray); // returns the index
}
#include "stdafx.h"
#include <limits>
using namespace std;
static const int array_len = 5;
double myarray[array_len] = { 1.0, 1.2, 1.4, 1.5, 1.9 };
int approx_search(const double val)
{
double min_val = numeric_limits<double>::max();
int index = 0;
for(int i=0;i<array_len;++i)
{
double diff = abs(myarray[i] - val);
if(diff<min_val)
{
min_val = diff;
index = i;
}
}
return index;
}
int _tmain(int argc, _TCHAR* argv[])
{
printf("approximate %d\n",approx_search(1.6));
printf("approximate %d\n",approx_search(1.7996));
printf("approximate %d\n",approx_search(1.4996));
printf("approximate %d\n",approx_search(0.0002));
return 0;
}