Binary Search Vector For Closest Value

[KB93]

Like the title says I am trying to use a binary search method to search a sorted vector for the closest given value and return its index. I have attempted to use lower/upper_bound() but the returned value is either the first or last vector value or 0. Below is the txt file which i have read the temp and voltage into vectors.

1.4	1.644290	-12.5
1.5	1.642990	-13.6
1.6	1.641570	-14.8
1.7	1.640030	-16.0
1.8	1.638370	-17.1

This is my current linear search that works

double Convert::convertmVtoK(double value) const
{
    assert(!mV.empty());
    auto it = std::min_element(mV.begin(), mV.end(), [value] (double a, double b) {
        return std::abs(value - a) < std::abs(value - b);
    });
    assert(it != mV.end());
    int index = std::distance(mV.begin(), it);
    std::cout<<kelvin[index];
    return kelvin[index];
}

This is the algorith I am currently trying to get working to improve performance.

double Convert::convertmVtoK(double value)
{
    auto it = lower_bound(mV.begin(), mV.end(), value);

    if (it == mV.begin())
    {
        it = mV.begin();
    }
    else
    {
        --it;
    }

    auto jt = upper_bound(mV.begin(), mV.end(), value), out = it;

    if (it == mV.end() || jt != mV.end() && value - *it > *jt - value)
    {
        out = jt;
    }

     cout<<"This is conversion mV to K"<<" "<< *out;

Any suggestions would be much appreciated.

[KB93]

This works

double Convert::convertmVtoK(double value) const
{

    auto it = lower_bound(mV.begin(), mV.end(), value, [](double a, double b){ return a > b; });
    int index = std::distance(mV.begin(), it);
    std::cout<<kelvin[index];
    return kelvin[index];
}

[dutch]

lower_bound returns lowest element >= value.
upper_bound returns lowest element > value.
If value is > all values in the vector then both will return end().

If the exact value doesn't exist then the iterators returned from lower_bound and upper_bound will be the same; i.e., they will both be the lowest element > value (or end()).

If the exact value does exist, then they will be different. The lower_bound iterator will be the lowest positioned element that equals the value; the upper_bound iterator will be one past the last element that equals the value (possibly end()). That way you can find a group of equal elements. In your case since you have no duplicates that doesn't apply so there's no point using both.

However, using lower_bound as you are doing is not quite right, either. And you don't need to convert the iterator to an index to access the value. You can "dereference" the iterator with *it. But if the value you searched for is greater than the highest value, lower_bound will return end(), which can't be dereferenced.

Here's an example that returns the value that is closest to the value you are looking for.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int search(vector<int> &v, int value)
{
    auto it = lower_bound(v.begin(), v.end(), value);
    if (it == v.end())
        return v.back();   // return last element
    auto found = *it;
    if (it != v.begin())
    {
        auto found2 = *(--it);
        if (abs(value - found2) < abs(value - found))
            found = found2;
    }
    return found;
}

int main()
{
    vector<int> v {3, 5, 9, 12, 13, 15};
    std::cout << search(v,  1) << '\n';  // 3
    std::cout << search(v, 10) << '\n';  // 9
    std::cout << search(v, 11) << '\n';  // 12
    std::cout << search(v, 99) << '\n';  // 15
}

But note that the searched for value could be much less than the lowest or much greater than the highest, so it's hard to see the relevance of returning the corresponding value. Why wouldn't you use an equation for this? What exactly are you trying to accomplish?

[KB93]

This is what I ended up doing. @dutch thank you for all the help. I am now trying to modify it for a struct.

double Convert::convertmVtoK(double value) const
{

    auto it = lower_bound(mV.begin(), mV.end(), value, [](double a, double b){ return a > b; });
    int index = std::distance(mV.begin(), it);

    if(value>mV[0] || value < mV.back())
    {
        std::cout<<"Warning: Voltage Out of Range"<<"\n";
    }

    else if(value==mV[0] || value==mV.back()
            ||fabs(value - mV[index]) <= 0.0001 * fabs(value))
    {
        std::cout<<kelvin[index];
        return kelvin[index];
    }

    else
    {
        double diff1 = std::abs(value - mV[index]);
        double diff2 = std::abs(value - mV[index-1]);

        if (diff2 < diff1)
        {
            std::cout<<kelvin[index-1];
            return kelvin[index-1];
        }

        else
        {
            std::cout<<kelvin[index];
            return kelvin[index];
        }
    }
}

[KB93]

So one problem I am having now is declaring the struct. If i declare it in the header file it says the type is not recognized in the .cpp file. Do i declare it directly in the class?

[jonnin]

if you declared the struct properly in the header and included it, it will work.

[dutch]

I also have no idea what the problem is there. The devil's in the details.

Here's a (rough and untested) possibility for translating your code above to work with a struct:

struct Record {
    double kelvin, mV, whatever;
};

double Convert::convertmVtoK(double value) const
{
    // If it's really close to one of those values then you
    // probably don't want to consider it an error.
    if (value > records.front().mV + 0.5 ||
        value < records.back().mV  - 0.5)
    {
        std::cout << "Warning: mV Out of Range\n";
        return 0.0;
    }

    auto it1 = lower_bound(records.begin(), records.end(), value,
                    [](const Record& r, double v){
                        return r.mV > v; });

    if (it1 == records.begin())
        return it1->kelvin;
    if (it1 == records.end())
        return records.back().kelvin;

    auto it2 = it1;
    --it2;

    if (std::abs(value - it1->mV) < std::abs(value - it2->mV))
        return it1->kelvin;
    else
        return it2->kelvin;
}

[KB93]

I guess my question now is how to access the struct member in the vector? Specifically at this point.

auto it = lower_bound(mV.begin(), mV.end(), value, [](double a, double b){ return a > b; });
    int index = std::distance(mV.begin(), it);

This is what I am trying. Going back to lookat what was just posted.

    auto it = std::lower_bound(response.front().mV, response.back().mV, value, [](double a, double b){ return a > b; });
    int index = std::distance(response.front().mV, it);

[KB93]

@dutch So this works except for the index. How can I get the index from it now? Will post if I figure it out.

    auto it = lower_bound(response.begin(), response.end(), value,
                    [](const TempResponse& r, double v){
                        return r.mV > v; });
    int index = std::distance(response.front(), it);

[dutch]

You shouldn't need the index, but if you want it you do it the same as with any vector:

int index = std::distance(response.begin(), it);

[KB93]

Final result for any Googlers out there in the future. Thank you @dutch for all the help, it is much appreciated and I hope you enjoy the new year!

double Convert::convertmVtoK(double value) const
{
    auto it = lower_bound(response.begin(), response.end(), value,
                    [](const TempResponse& r, double v){
                        return r.mV > v; });
    int index = std::distance(response.begin(), it);

    if(value>response[0].mV || value < response.back().mV)
    {
        std::cout<<"Warning: Voltage Out of Range"<<"\n";
    }

    else if(value==response[0].mV || value==response.back().mV
            ||fabs(value - response[index].mV) <= 0.0001 * fabs(value))
    {
        std::cout<<response[index].kelvin;
        return response[index].kelvin;
    }

    else
    {
        double diff1 = std::abs(value - response[index].mV);
        double diff2 = std::abs(value - response[index-1].mV);

        if (diff2 < diff1)
        {
            std::cout<<response[index-1].kelvin;
            return response[index-1].kelvin;
        }

        else
        {
            std::cout<<response[index].kelvin;
            return response[index].kelvin;
        }
    }
}

[KB93]

@dutch Actually one more question if you want to answer. So I have created another function that converts K to mV but am trying to get it to work with the struct now.

Original

double Convert::convertKtomV(double value) const
{
    auto it = lower_bound(kelvin.begin(), kelvin.end(), value);
    int index = std::distance(kelvin.begin(), it);

    if(value<kelvin[0] || value > kelvin.back())
    {
        std::cout<<"Warning: Temperature Out of Range"<<"\n";
    }

    else if(value==kelvin[0] || value==kelvin.back()
            ||fabs(value - kelvin[index]) <= 0.0001 * fabs(value))
    {
        std::cout<<mV[index];
        return mV[index];
    }

    else
    {

        double diff1 = std::abs(value - kelvin[index]);
        double diff2 = std::abs(value - kelvin[index-1]);

        if (diff2 < diff1)
        {
            std::cout<<mV[index-1];
            return mV[index-1];
        }

        else
        {
            std::cout<<mV[index];
            return mV[index];
        }

    }
}

I am having an issue with the auto it, im guessing because the Kelvin list is in ascending order. It returns all '0's.

      auto it = lower_bound(response.begin(), response.end(), value,
                    [](const TempResponse& r, double v){
                        return r.kelvin > v; });
    //int index = std::distance(response.begin(), *it);
    std::cout<<*it;

[KB93]

solved

double Convert::convertKtomV(double value) const
{
    auto it = lower_bound(response.begin(), response.end(), value,
                    [](const TempResponse& r, double v){
                        return r.kelvin < v; });
    int index = std::distance(response.begin(), it);
    std::cout<<index;