CODEWITHSUNDEEP
c++
user13948
user13948

Reputation: 453

std function lower bound is not working as expected?

I'm trying to get a method to return the closest value to 0.5, and used std::lower_bound. Why does this return the incorrect value, and a value that isn't even in the array? Worse, if I run it multiple times in a row it returns different answers. All I can think is it's in some way related to floats and decimal points but I can't pin it down. Thanks for any help!

#include <iostream>     
#include <algorithm>       
#include <vector> 


int test() {


float array[] = {0.730453, 0.699215, 0.669218, 0.637146, 0.604049, 0.572716, 0.541121, 0.50986, 0.47848, 0.449675, 0.419725, 0.3908, 0.363951, 0.338627, 0.312707, 0.289863, 0.26578, 0.244605, 0.224265, 0.204569, 0.185969, 0.169755, 0.155114, 0.140401, 0.126714, 0.115817, 0.104347, 0.0945466, 0.000119226, 9.53812e-05, 9.53812e-05, 7.15359e-05};   
std::vector<float> v(std::begin(array),std::end(array));
std::reverse(std::begin(array),std::end(array));
std::vector<float>::iterator low, up;
low=std::lower_bound (v.begin(), v.end(), 0.5);

std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
std::cout<<"index of thing is "<<low- v.begin()<<endl;
float & element = v[low- v.begin()];
std::cout<<"element closest to 0.5 is "<< element<<endl;
return 0;

            }

Upvotes: 1

Views: 875

Answers (3)

Caduchon
Caduchon

Reputation: 5201

This is a suggested method to find the closest value in a range if you don't know if it's sorted or not:

template <typename Iterator>
double closest_to(Iterator begin, Iterator end, double value)
{
    double min_dist = std::numeric_limits<double>::infinity();
    double min_val;
    for(Iterator it = begin; it != end; ++it)
    {
        const double dist = fabs(*it - value);
        if(dist < min_dist)
        {
            min_dist = dist;
            min_val = *it;
        }
    }
    return min_val;
}

Then, use it like that:

std::cout << closest_to(v.begin(), v.end(), 0.5) << std::endl;

If you know that your range is sorted, it is faster with this implementation:

template <typename ForwardIterator>
double closest_to(ForwardIterator begin, ForwardIterator end, double value)
{
  ForwardIterator lb = std::lower_bound(begin, end, value);
  if(lb == begin)
    return *lb;
  Iterator prev = lb - 1;
  if(lb == end)
    return *prev;
  if(value - *prev < *lb - value)
    return *prev;
  else
    return *lb;
}

Upvotes: 2

cigien
cigien

Reputation: 60218

Your vector needs to be sorted for lower_bound to return the correct result. If it's not sorted, then calling lower_bound invokes undefined behavior.

So before calling lower_bound, you need to do:

std::sort(v.begin(), v.end());

Here's a demo.

It seems that array is sorted in reverse order. So before constructing v you need to reverse array, not after.:

std::reverse(std::begin(array),std::end(array));  // first reverse
std::vector<float> v(std::begin(array),std::end(array));

Then there is no need to sort v.

Also, instead of reversing the array or v, you can just use reverse iterators:

std::lower_bound (v.rbegin(), v.rend(), 0.5);

or use a different predicate:

std::lower_bound (v.begin(), v.end(), 0.5, std::greater{});

Upvotes: 2

Caleth
Caleth

Reputation: 62636

your data needs to be ordered to use lower_bound. The default order is <, but you can specify a different ordering, such as > (via std::greater).

#include <iostream>     
#include <algorithm>       
#include <vector> 

int test() {

    float array[] = {0.730453, 0.699215, 0.669218, 0.637146, 0.604049, 0.572716, 0.541121, 0.50986, 0.47848, 0.449675, 0.419725, 0.3908, 0.363951, 0.338627, 0.312707, 0.289863, 0.26578, 0.244605, 0.224265, 0.204569, 0.185969, 0.169755, 0.155114, 0.140401, 0.126714, 0.115817, 0.104347, 0.0945466, 0.000119226, 9.53812e-05, 9.53812e-05, 7.15359e-05};   
    std::vector<float> v(std::begin(array),std::end(array));
    std::reverse(std::begin(array),std::end(array));
    std::vector<float>::iterator low, up;
    low=std::lower_bound (v.begin(), v.end(), 0.5, std::greater<float>{});
    
    std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
    std::cout<<"index of thing is "<<low- v.begin()<<std::endl;
    float & element = v[low- v.begin()];
    std::cout<<"element closest to 0.5 is "<< element<<std::endl;
    return 0;

}

Upvotes: 0

Related Questions