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