Как найти наиболее точный промежуток?

Question

[wangler]

Здравствуйте.
Подскажите алгоритм, по которому я смогу найти максимально точный промежуток с минимумом запросов. Возможно это уже предусмотрено в MySQL.
есть таблица с отрезками (start, end) и значение, которое надо найти c наиболее точным вхождением.
Например, есть таблица с интервалами:

|  id   |        start          |           end      |
|  1    |        10             |         1000       |
|  2    |        100            |          125       |
|  3    |        50             |          3000      |

при поиске значения 101 хотелось бы получить именно интервал с id=2, ведь он наиболее точный.
Благодарю за подсказки!

Answer 1

[Rsa97]

1. Математически формализовать понятие "наиболее точный", составить формулу метрики.
2. Выбрать все интервалы, где :value BETWEEN `start` AND `end` и посчитать для них метрику.
3. Отсортировать по метрике.
4. Выбрать первую строку из сортированного списка.

Comments

[Андрей]

Насколько я понимаю, здесь автор под метрикой понимает (end-start), соответственно в запросе ему нужен MIN(END-START) WHERE value BETWEEN `start` AND `end`

[Rsa97]

Андрей: Не знаю. Например, что точнее для значения 100: [98; 100], [99; 101] или [100; 102]?

[Макс]

Андрей: может быть наиболее близкий к среднему, наиболее близкий к одной из границ, наименьший диапазон.

[evgeniy_lm]

Математически это выглядит так value BETWEEN (START, END) and MIN(END-START) and MIN(START- value) and MIN(END-value)

[Rsa97]

evgeniy_lm: Это вы не подумав написали. Для значения 100 из двух интервалов [99; 100] и [98; 101] ваш запрос не выберет ни одного, так как MIN(END-START) = 1 у первого интервала, а MIN(START-value) = -2 у второго.

Answer 2

[guras256]

select t.id from ranges t 
where &value between t.start and t.end -- сначала отсекаем диапазоны, в которые точно не попадаем
order by t.end - t.start -- определяем "наиболее точный" диапазон как наименьший удовлетворяющий и сортируем по нему в порядке возрастания.

таким образом, первая запись будет самая подходящая
рабочий пример