Всем привет!
Подскажите пожалуйста быстрый, по возможности не сложный, алгоритм решения такой задачи.
У меня есть отсортированный большой массив с интервалами "beg" и "end".
И есть некий отрезок, например: [30, 60].
Нужно найти все пересечения этого отрезка с интервалами в массиве.
Самое простое это линейный поиск:
var intervals = [
{beg: 8, end: 16},
{beg: 24, end: 32},
{beg: 40, end: 48},
{beg: 56, end: 64},
{beg: 72, end: 80},
{beg: 88, end: 96}
];
var range = [30, 60];
var overlap = [];
for(i = 0; i < intervals.length; i++)
{
var A = intervals[i].beg;
var B = intervals[i].end;
if(range[0] <= B && range[1] >= A)
{
overlap.push( intervals[i] );
}
}
console.log(overlap);
Все работает, и в результате мы получим массив интервалов с которым полностью или частично пересекается наш диапазон:
{beg: 24, end: 32}
{beg: 40, end: 48}
{beg: 56, end: 64}
Но в этой реализации слишком много лишних итераций.
Первое что пришло в голову по оптимизации это бинарный поиск первого левого пересечения и добивка линейным поиском.
И тут проблема.
Я могу найти элемент в массиве "intervals" только если есть точное совпадение например "beg" с началом отрезка.
А как найти элемент между двумя значениями не могу придумать.