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

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

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

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

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

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

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) );

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

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

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

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

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

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

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