Быстрый поиск интервалов в массиве

[HJ90]

Всем привет!
Подскажите пожалуйста быстрый, по возможности не сложный, алгоритм решения такой задачи.

У меня есть отсортированный большой массив с интервалами "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" с началом отрезка.
А как найти элемент между двумя значениями не могу придумать.

[рони]

HJ90,
буду приятно удивлён, если кто-то предложит лучше вариант, чем у вас.

[HJ90]

HJ90,
буду приятно удивлён, если кто-то предложит лучше вариант, чем у вас.

Спасибо за ответ!
Лучше может быть оптимизация линейного поиска.
Например прерывать цикл, если слева мы непрерывно что-то нашли, а после этого уже нет перекрытия - тогда искать до конца массива уже нет смысла.

Но это незначительная оптимизация. Прирост производительности будет только если искомие элементы находятся вначале массива.

[Alexandroppolus]

Разумеется, тут можно применить поиск делением пополам. Если отрезки массива не пересекаются между собой, то всё довольно просто.

[HJ90]

Alexandroppolus, а можете хотя бы в двух словах описать как бинарным поиском найти элемент в котором есть диапазон значений от 40 до 48?

Отрезки не пересекаются между собой. Но вот че-то я туплю уже второй день.

Например если за основу взять такую функцию бинарного поиска, то мы найдем элемент с индексом 2:

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}
];

function bin_search(arr, val)
{
	var min = 0;
	var max = arr.length - 1; 
	
	while (min < max)                
	{	
		var mid = Math.floor((min + max) / 2);
		
		if(arr[mid].beg < val) {min = mid + 1}
		
		else max = mid;
	}
	if(arr[min].beg == val)
	{
		return {index:min};
	}
	return -1;
}
console.log( bin_search(intervals, 40) );

[ksa]

тут можно применить поиск делением пополам

Хорошая идея.

а можете хотя бы в двух словах описать

Ведь у тебя массив отсортирован...

Предложу такой вариант.
- Берем элемент "посередине" массива.
- Узнаем как его "положение" корелирует с нашим отрезком. Т.е. мы ниже, выше, или внутри предполагаемого подмассива.
- Если внутри, значит идем ниже, пока есть пересечение. А потом выше, пока не кончится пересечение.
- Если ниже, делим нижнюю часть пополам и опять проверяем наше местоположение.
- Если выше, делим верхнюю часть пополам и опять проверяем наше местоположение.

Но это довольно сложный алгоритм и смысл в нем есть если массив тот реально здоровенный! А отрезок мал...

[Nexus]

HJ90,
А массив данных, который присутствует в коде от балды заполнен или это действительно используемые данные?

[laimas]

Если внутри, значит идем ниже, пока есть пересечение. А потом выше, пока не кончится пересечение.

Тогда сразу двигаться вниз и вверх.

[HJ90]

ksa, спасибо за Ваше предложение! Буду пробовать реализовывать.
Nexus, массив заполнен от балды. А в реале значения какие угодно могут быть, всегда по возрастанию и не пересекаются.

[ksa]

Тогда сразу двигаться вниз и вверх.

Это уже как тебе угодно...