std::upper_bound/lower_bound 같은 탐색이 가장 빠른 자료구조

어떤 정렬된 값들이 주어졌을 때, 특정 값이 어디사이에 포함되는지를 가장 빠르게 찾고 싶습니다.
값들은 전부 실수(double)입니다.

예를 들어 지금은 std::map[double, T] (꺽쇠를 매번 엔티티로 적어주는게 귀찮아서 []로 적겠습니다) 를 이용하고 있는데,

std::map[double, int] map;
map[0.1] = 1;
map[0.5] = 0;
map[2.1] = 3;
...

이런식으로 들어있을 때, 0.7이란 key가 map안에서는 (0.5, 0)과 (2.1, 3)사이에 있다는 것을 찾아내기 위해서
auto it = --map.upper_bound(0.7); // it == pair(0.5, 0)
처럼 위치를 가져오고 있습니다.
보통은 이진탐색 정도면 나쁘지 않은 속도인데, 탐색자체를 짧은 시간안에 매우 자주해야되다보니 탐색시간이 무시못할게 되버렸습니다.
key검색만 하면 된다면 hash table을 써볼텐데, key와 key사이의 구간을 찾아야되서 이건 쓸수가 없네요.
수치계산에서 이용하기 때문에 무조건 빠를수록 좋습니다.
전체 계산시간에 비하면 탐색시간은 길지 않지만, 전체 시간자체가 길다보니, 이 짧은 시간이라도 어떻게 절약하고 싶습니다.

조건은

1. map이나 정렬된 vector보다 빠르게 upper_bound같은 특정 구간값을 찾는게 가능한 자료구조
2. 삽입/삭제는 처음에 초기화할때만 이루어지기 때문에 삽입/삭제는 느려도 됨
3. 검색/정렬 key는 double만 쓰기 때문에, double에 특화된 자료구조도 상관없음
4. key는 중복되지 않음
(4. 기왕이면 STL과 호환가능한 C++ template container 소스가 존재하면 좋음)

알고 계신게 있으시다면 소개부탁드립니다.