Wyszukaj najbliższą wartość w tablicy podwójnej w C++?

Question

Mam posortowaną tablicę podwójnych wartości w C++. Czy istnieje funkcja STL, która zwróci indeks z najbliższej wartości najbliższej w tablicy do danej wartości podwójnej?

Na przykład, biorąc pod uwagę co następuje tablica

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

wywołanie funkcji

search(myarray, 1.6); 

powinna powrócić 3 indeks elementu najbliższego 1,6 zamiast -1 (lub inną wartość flagi) wskazując, że nie znaleziono wartości 1.6.

Answer 1

może std::lower_boundstd::upper_bound pomoże.

Answer 2

Czy tablica ma być w porządku rosnącym? Jeśli tak, nadaj mu wygląd: std::lower_bound.

Answer 3

Myślę, że mój przykład zrobić dokładnie to, co chcesz:

(używam std :: min_element oraz funktor)

#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

Oto ogólny rozwiązanie wykorzystujące 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; 
} 

Zauważysz, że użyłem dwukierunkowych Iteratorów, co oznacza, że ​​funkcja może działać tylko z iteratorami, które mogą być zarówno inkrementowane, jak i zmniejszane. Lepsza implementacja narzuciłaby jedynie koncepcję Input Iterators, ale dla tego problemu powinno to być wystarczająco dobre.

Ponieważ chcesz indeksu i nie iterator, można napisać niewiele funkcji pomocnika:

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

a teraz skończyć z kodu:

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

co daje następujące wyniki:

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