Поиск ближайшего значения в массиве двойников в C++?

Question

У меня есть отсортированный массив двойных значений в 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 не найдено.

Answer 1

возможно std::lower_boundstd::upper_bound поможет вам.

Answer 2

Возможно, объект массирован по возрастанию? Если да, то посмотрите std::lower_bound.

Answer 3

Я думаю, что мой пример делать именно то, что вы хотите:

(я использую зЬй :: min_element и функтор)

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

Answer 4

Здесь общее решение с использованием 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 

Answer 5

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