SashaMercuryAkinaпропущено...

В таком случае можно в качестве предобработки поделить весь интервал, покрываемый этими интервалами (min(start)...max(end)) на набор непрерывных отрезков, и составить таблицу, располагается ли конкретный частный интервал на каждом из отрезков, с градацией полностью/частично. Тогда по заданной координате половинным делением получаем сразу список частных интервалов, которые следует проверять на попадание в них точки (те, что частично), и список тех, в которые точка гарантированно попадает (те, что полностью).
Думать, на какое количество отрезков оптимально рубить диапазон, лениво... тем более думать о том, что в оптимуме они могут быть неравными по размеру.

А если длину каждого отрезка устремить к нулю(ведь объем предварительных расчётов нас не волнует), то результирующая асимптотика будет O(1).
Можно решать биткартой числовой картой. С некоторым приближением будет почти O(1).
Или выродить задачу в мемоизацию всего что может приходить на вход.