The first number less than or equal to a needle

2015-11-17

How do you find the first number less than or equal to a needle in an STL container? The following code does this and provides tests to ensure things are working as expected. Although the code is written for a vector, it could be adapted to any container providing a ForwardIterator.

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

//Find the largest number less than or equal to a needle number
double FindLargestLessThanEqualNeedle(const std::vector<double> &v, double needle){
  auto up = std::upper_bound(v.begin(), v.end(), needle);
  if(up==v.begin())
    return v.front();
  else if(up==v.end())
    return v.back();
  else
    return *(up-1);
}

//Find the index of the largest number less than or equal to a needle number
size_t FindLargestLessThanEqualNeedleIdx(const std::vector<double> &v, double needle){
  auto up = std::upper_bound(v.begin(), v.end(), needle);
  if(up==v.begin())
    return 0;
  else if(up==v.end())
    return v.size()-1;
  else
    return up-v.begin()-1;
}

int main(){
  std::vector<double> v={{0,1,4,8,10,15,20}};
  std::cout<<FindLargestLessThanEqualNeedle(v,-1)<<std::endl;
  std::cout<<FindLargestLessThanEqualNeedle(v,25)<<std::endl;
  std::cout<<FindLargestLessThanEqualNeedle(v,8)<<std::endl;
  std::cout<<FindLargestLessThanEqualNeedle(v,9)<<std::endl;
  std::cout<<FindLargestLessThanEqualNeedle(v,10)<<std::endl;

  std::cout<<FindLargestLessThanEqualNeedleIdx(v,-1)<<std::endl;
  std::cout<<FindLargestLessThanEqualNeedleIdx(v,25)<<std::endl;
  std::cout<<FindLargestLessThanEqualNeedleIdx(v,8)<<std::endl;
  std::cout<<FindLargestLessThanEqualNeedleIdx(v,9)<<std::endl;
  std::cout<<FindLargestLessThanEqualNeedleIdx(v,10)<<std::endl;
}

Richbits