Первый способ тоже годится, но фактически для непересекающихся множеств можно пользоваться только одной границей.
CREATE TABLE IF NOT EXISTS `test1` (
  `minVal` int(11) NOT NULL,
  `maxVal` int(11) NOT NULL,
  `price` int(11) NOT NULL AUTO_INCREMENT,
  PRIMARY KEY (`price`),
  UNIQUE KEY `froms` (`minVal`),
  UNIQUE KEY `fr2` (`minVal`,`maxVal`)
) ENGINE=MyISAM;
заполним ее значениями для 100к множеств с шагом 5 (0..4,5..9,… ,100000..100005)
EXPLAIN SELECT * 
FROM  `test1` 
WHERE minval <=42000
ORDER BY minval DESC 
LIMIT 1
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE test1 range froms,fr2 fr2 4 NULL 9396 Using where
EXPLAIN SELECT * 
FROM  `test1` 
WHERE minval <=42000
AND maxval >=42000
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE test1 ALL froms,fr2 NULL NULL NULL 20001 Using where
Имеющий глаза — да увидит.