Показать сообщение отдельно
  #5 (permalink)  
Старый 16.08.2017, 13:17
Аспирант
Отправить личное сообщение для HJ90 Посмотреть профиль Найти все сообщения от HJ90
 
Регистрация: 24.07.2012
Сообщений: 37

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) );
Ответить с цитированием