Binary Search Vector for Closest Value C++

Question

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 algorithm 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. I believe the issue may lie with the vector being sorted in descending order but i need the order to remain the same in order to compare the values.

SOLVED thanks to @John. For anyone who needs this in the future here is what 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];
}

Answer 1

Since you have a non-increasing range (sorted in descending order), you can use std::lower_bound with a greater than operator, as mentioned in comments. However, this only gets you the first result past or equal to your number. It doesn't mean it's the "closest", which is what you asked for.

Instead, I would use std::upper_bound, so you don't have to check for equality (on double just to make it worse) and then drop back one to get the other bounding data point, and compute which one is actually closer. Along with some boundary checks:

#include <vector>
#include <algorithm>
#include <iostream>
#include <functional>
#include <iterator>

// for nonincreasing range of double, find closest to value, return its index
int index_closest(std::vector<double>::iterator begin, std::vector<double>::iterator end, double value) {
    if (begin == end){
        // we're boned
        throw std::exception("index_closest has no valid index to return");
    }

    auto it = std::upper_bound(begin, end, value, std::greater<double>());

    // first member is closest
    if (begin == it)
        return 0;

    // last member is closest. end is one past that.
    if (end == it)
        return std::distance(begin, end) - 1;

    // between two, need to see which is closer
    double diff1 = abs(value - *it);
    double diff2 = abs(value - *(it-1));
    if (diff2 < diff1)
        --it;
    return std::distance(begin, it);
}

int main()
{
    std::vector<double> data{ -12.5, -13.6, -14.8, -16.0, -17.1 };
    for (double value = -12.0; value > -18.99; value = value - 1.0) {
        int index = index_closest(data.begin(), data.end(), value);
        std::cout << value << " is closest to " << data[index] << " at index " << index << std::endl;
    }
}

output

-12 is closest to -12.5 at index 0
-13 is closest to -12.5 at index 0
-14 is closest to -13.6 at index 1
-15 is closest to -14.8 at index 2
-16 is closest to -16 at index 3
-17 is closest to -17.1 at index 4
-18 is closest to -17.1 at index 4

Note that, e.g. -14 is closer to -13.6 than -14.8, as a specific counterexample to your current working point. Also note the importance of inputs at both end points.

From there you are welcome to take kelvin[i]. I wasn't happy with using an external data array for the function's return value when you don't need to do that, so I just returned the index.

Answer 2

You might use the following to get the iterator with closest value:

auto FindClosest(const std::vector<double>& v, double value)
{
    // assert(std::is_sorted(v.begin(), v.end(), std::greater<>{}));
    auto it = std::lower_bound(v.begin(), v.end(), value, std::greater<>{});

    if (it == v.begin()) {
        return it;
    } else if (it == v.end()) {
        return it - 1;
    } else {
        return std::abs(value - *it) < std::abs(value - *(it - 1)) ?
               it : it - 1;
    }
}