Поиск диапазона в Java

Предположим, у меня есть несортированный массив перекрывающихся диапазонов . Каждый диапазон - это просто пара целых чисел begin и end . Теперь я хочу определить, принадлежит ли данный ключ хотя бы одному из диапазонов . Наверное, мне нужно знать диапазоны , которым он тоже принадлежит.

Мы можем предположить, что массив range занимает ~ 1M и умещается в памяти. Я ищу простой алгоритм, который использует только стандартные коллекции JDK без каких-либо сторонних библиотек и специальных структур данных, но работает достаточно быстро.

Что бы вы посоветовали?