Rechercher la valeur la plus proche dans un tableau de doubles en C++?

Question

J'ai un tableau trié de valeurs doubles en C++. Existe-t-il une fonction LIST qui renvoie l'indice de la valeur la plus proche dans le tableau à une valeur double donnée?

Par exemple, étant donné le tableau suivant

double myarray[5] = { 1.0, 1.2, 1.4. 1.5, 1.9 }; 

l'appel de fonction

search(myarray, 1.6); 

doit retourner 3, l'indice de l'élément le plus proche de 1,6, au lieu de -1 (ou une autre valeur de drapeau) indiquant que la valeur 1,6 n'a pas été trouvée.

Answer 1

peut-être std::lower_boundstd::upper_bound vous aidera.

Answer 2

Le tableau est-il garanti dans l'ordre croissant? Si oui, donnez un std::lower_bound un coup d'oeil.

Answer 3

Je pense que mon exemple faire exactement ce que vous voulez:

(j'utilise std :: min_element et un foncteur)

#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

Voici une solution générique avec 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; 
} 

Vous remarquerez que j'ai utilisé des itérateurs bidirectionnels, ce qui signifie que la fonction ne peut fonctionner qu'avec des itérateurs qui peuvent être incrémentés et décrémentés. Une meilleure implémentation n'imposerait que le concept des Iterators d'entrée, mais pour ce problème, cela devrait être suffisant.

Puisque vous voulez l'index et non un itérateur, vous pouvez écrire une petite fonction d'aide:

template <typename BidirectionalIterator, typename T> 
std::size_t getClosestIndex(BidirectionalIterator first, 
          BidirectionalIterator last, 
          const T & value) 
{ 
    return std::distance(first, getClosest(first, last, value)); 
} 

Et maintenant, vous vous retrouvez avec un code comme ceci:

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

qui donne la résultats suivants:

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