16.08.2017, 14:10
|
|
Профессор
|
|
Регистрация: 14.01.2015
Сообщений: 12,989
|
|
|
Сообщение от ksa
|
|
Это уже как тебе угодно...
|
Если речь об оптимизации, то обход массива можно производить с двух концов сразу, к центру, можно и наоборот, что уменьшит число итераций. Вот только если угадали с центром, то хорошо, а если нет, то ... искомое или в начале может быть, или в конце и т.д. А мне в общем-то все равно, не мне же нужно.  |
|
16.08.2017, 14:16
|
 |
CacheVar
|
|
Регистрация: 19.08.2010
Сообщений: 14,298
|
|
|
Сообщение от laimas
|
|
Если речь об оптимизации, то обход массива можно производить ...
|
Метод "деления пополам" это вего лишь один из способов работы с массивами. На большее я не претендую...  |
|
16.08.2017, 20:17
|
|
Аспирант
|
|
Регистрация: 24.07.2012
Сообщений: 37
|
|
Пока вот так - возвращает первый слева элемент который пересекается с входным диапазоном.
Осталось найти все интервалы когда входной диапазон большой.
<html>
<span> [8-16] [24-32] [40-48] [56-64] [72-80] [88-96] </span>
<br>
<input type="number" value="8" oninput="test()" /> и
<input type="number" value="" disabled="true" /> пересекается с
<input id="result" disabled="true" />
<style>
body {text-align:center}
span {display:inline-block; padding:15px; font-size:18px; font-family:consolas}
input {width:100px; height:50px; font-size:35px; text-align:center}
</style>
<script>
window.onload = test;
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 test(value)
{
var A = +document.querySelectorAll("input")[0].value;
var B = A + 2;
document.querySelectorAll("input")[1].value = B;
function bin_search_range(arr, A)
{
var min = 0;
var max = arr.length - 1;
while (min < max)
{
var mid = Math.floor((min + max) / 2);
if(arr[mid].end < A)
{
min = mid + 1;
}
else max = mid;
}
if(arr[min].beg <= B && arr[min].end >= A)
{
return arr[min].beg + "-" + arr[min].end;
}
return "...";
}
document.querySelector("#result").value = bin_search_range(intervals, A);
}
</script>
</html>
|
|
16.08.2017, 20:52
|
 |
Профессор
|
|
Регистрация: 25.10.2016
Сообщений: 1,013
|
|
|
Если диапазон большой и охватывает много интервалов, то лучше всего найти индексы первого и последнего интервалов (оба поиска - бинарные). Возможно, копировать все интервалы между ними в отдельный массив необязательно.
|
|
16.08.2017, 21:19
|
 |
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,150
|
|
оптимизация: цикл только по "нужным" элементам, после найденного первого. (проще конечно for и break)
можно вводить в диапазон оба параметра
<html><meta charset="utf-8">
<span> [8-16] [24-32] [40-48] [56-64] [72-80] [88-96] </span>
<br>
<input type="number" value="8" oninput="test()" /> и
<input type="number" value="28" oninput="test()" /> пересекается с
<input id="result" disabled="true" style="width: 500px;font-size:12px; "/>
<style>
body {text-align:center}
span {display:inline-block; padding:15px; font-size:18px; font-family:consolas}
input {width:100px; height:50px; font-size:35px; text-align:center}
</style>
<script>
window.onload = test;
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 test(value) {
var A = +document.querySelectorAll("input")[0].value;
var B = +document.querySelectorAll("input")[1].value;
function bin_search_range(arr, A) {
var min = 0;
var max = arr.length - 1;
var temp = [];
while (min < max) {
var mid = Math.floor((min + max) / 2);
if (arr[mid].end < A) min = mid + 1;
else max = mid
}
if (arr[min].beg <= B && arr[min].end >= A) {
arr.slice(min).some(function(el) {
return !(el.beg <= B && el.end >= A && temp.push(el))
});
return JSON.stringify(temp)
}
return "..."
}
document.querySelector("#result").value = bin_search_range(intervals,A)
};
</script>
</html>
|
|
16.08.2017, 21:39
|
|
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,150
|
|
|
Сообщение от Alexandroppolus
|
|
то лучше всего найти индексы первого и последнего интервалов
|
<html><meta charset="utf-8">
<span> [8-16] [24-32] [40-48] [56-64] [72-80] [88-96] </span>
<br>
<input type="number" value="78" oninput="test()" /> и
<input type="number" value="90" oninput="test()" /> пересекается с
<input id="result" disabled="true" style="width: 500px;font-size:12px; "/>
<style>
body {text-align:center}
span {display:inline-block; padding:15px; font-size:18px; font-family:consolas}
input {width:100px; height:50px; font-size:35px; text-align:center}
</style>
<script>
window.onload = test;
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 test(value) {
var A = +document.querySelectorAll("input")[0].value;
var B = +document.querySelectorAll("input")[1].value;
function bin_search_range(arr) {
var min = 0;
var max = arr.length - 1;
var temp;
while (min < max) {
var mid = Math.floor((min + max) / 2);
if (arr[mid].end < A) min = mid + 1;
else max = mid
}
max = arr.length - 1;
temp = min
while (min < max) {
var mid = Math.floor((min + max) / 2);
if (arr[mid].beg < B) min = mid + 1;
else max = mid
}
if (arr[temp].beg <= B && arr[temp].end >= A) {
if (arr[min].beg <= B && arr[min].end >= A) ++min;
return JSON.stringify(arr.slice(temp,min))
}
return "..."
}
document.querySelector("#result").value = bin_search_range(intervals)
};
</script>
</html>
Последний раз редактировалось рони, 16.08.2017 в 21:43.
|
|
16.08.2017, 22:38
|
|
Аспирант
|
|
Регистрация: 24.07.2012
Сообщений: 37
|
|
|
рони, то что нужно!) Всем больше спасибо за помощь!
|
|
16.08.2017, 23:20
|
|
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,150
|
|
HJ90,
<html><meta charset="utf-8">
<span> [8-16] [24-32] [40-48] [56-64] [72-80] [88-96] </span>
<br>
<input type="number" value="18" oninput="test()" /> и
<input type="number" value="59" oninput="test()" /> пересекается с
<input id="result" disabled="true" style="width: 500px;font-size:12px; "/>
<style>
body {text-align:center}
span {display:inline-block; padding:15px; font-size:18px; font-family:consolas}
input {width:100px; height:50px; font-size:35px; text-align:center}
</style>
<script>
window.onload = test;
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 test(value) {
var A = +document.querySelectorAll("input")[0].value;
var B = +document.querySelectorAll("input")[1].value;
function bin_search_range(arr) {
for (;arr.length; ) {
if (arr[0].beg <= B && arr[0].end >= A) {
break;
}
arr = arr.slice(1);
}
var i=arr.length;
for (; i-- ;) {
if (arr[i].beg <= B && arr[i].end >= A) {
arr = arr.slice(0,++i); break;
}
}
if (arr.length) {
return JSON.stringify(arr)
}
return "..."
}
document.querySelector("#result").value = bin_search_range(intervals)
};
</script>
</html>
|
|
16.08.2017, 23:28
|
|
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,150
|
|
HJ90,
<html><meta charset="utf-8">
<span> [8-16] [24-32] [40-48] [56-64] [72-80] [88-96] </span>
<br>
<input type="number" value="18" oninput="test()" /> и
<input type="number" value="59" oninput="test()" /> пересекается с
<input id="result" disabled="true" style="width: 500px;font-size:12px; "/>
<style>
body {text-align:center}
span {display:inline-block; padding:15px; font-size:18px; font-family:consolas}
input {width:100px; height:50px; font-size:35px; text-align:center}
</style>
<script>
window.onload = test;
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 test(value) {
var A = +document.querySelectorAll("input")[0].value;
var B = +document.querySelectorAll("input")[1].value;
function bin_search_range(arr) {
for (;arr.length; ) {
if (arr[0].beg <= B && arr[0].end >= A) {
break;
}
arr = arr.slice(1);
}
for (var i=0; i<arr.length; i++) {
if (arr[i].beg <= B && arr[i].end >= A) continue;
else {arr = arr.slice(0,i); break;}
}
if (arr.length) {
return JSON.stringify(arr)
}
return "..."
}
document.querySelector("#result").value = bin_search_range(intervals)
};
</script>
</html>
|
|
16.08.2017, 23:49
|
|
Аспирант
|
|
Регистрация: 24.07.2012
Сообщений: 37
|
|
|
рони, круто! Правда с бинарным поиском меньше итераций получается.
|
|
|
|
