find interval from value

Question

Suppose I've a list of intervals: [1, 90], [104, 234], [235, 300], .... Every interval has a name A1, B, B1, .... Given a value I want the name of the interval (112 -> B, 100 -> special_value). What's the best and faster implentation? Something better than a list of if / else if.

The intervals are sorted in order, and there is no overlap. I have a lot of values as input, but only one set of intervals. The size intervals are very different, some are very small, other are very large.

Answer 1

Idea: make a map object for the begin value of interval. If we found the possible interval, check if the value is in the interval.

class MyInterval
{
public:
  MyInterval( double begin, double end )
  : m_begin(begin), m_end(end)
  {
  };
  double m_begin, m_end;
};

bool operator < (  const MyInterval& left,  const MyInterval& right )
{
  return ( left.m_begin < right.m_begin );
}

std::map<MyInterval,std::string> store;
// use upper_bound to get the place+1 and then you could check the interval
std::map<MyInterval,std::string>::iterator iter = store.upper_bound( MyInterval(value,value) );
if ( iter != store.begin() )
{
  --iter;
  if ( iter->first.m_end >= value ) 
  {
    std::string result_text = iter->second;
    // Here is your result
  }
}

More info: link.

It was tested in Visual Studio 2010.