¿Busca el valor más cercano en una matriz de dobles en C++?

Question

Tengo una matriz ordenada de valores dobles en C++. ¿Hay una función STL que devolverá el índice del valor más cercano en la matriz a un valor doble dado?

Por ejemplo, dada la siguiente matriz

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

la llamada de función

search(myarray, 1.6); 

debe devolver 3, el índice del elemento más cercano a 1.6, en lugar de -1 (o algún otro valor de bandera) que indica que no se encontró el valor 1.6.

Answer 1

tal vez std::lower_boundstd::upper_bound le ayudará.

Answer 2

¿Está garantizado que la matriz está en orden ascendente? Si es así, denle un vistazo a std::lower_bound.

Answer 3

Creo que mi ejemplo hacer exactamente lo que quiere:

(yo uso std :: min_element y un funtor)

#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

que aquí hay una solución genérica utilizando 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; 
} 

Notarás que utilicé Iterators Bidireccionales, lo que significa que la función solo puede funcionar con iteradores que pueden incrementarse y decrementarse. Una mejor implementación solo impondría el concepto de Iteradores de entrada, pero para este problema, esto debería ser lo suficientemente bueno.

Desde desea que el índice y no un iterador, puede escribir un poco de función auxiliar:

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

Y ahora se termina con un código como este:

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

que da la siguientes resultados:

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