Бинарный поиск в JavaScript. Практический пример

[RuGrof]

Хм… у вас отрезок разделённый на 30 равных частей, координаты его начала и конца, координаты курсора. Вы уверены, что вам нужен поиск, чтоб определить к какой из частей, курсор находится ближе?

[merovinh]

согласен с автором статьи, что если объем данных большой, то использование бинарного поиска будет вполне оправдано. Здесь же простой пример где просто для наглядности показано как это работает

[Aquahawk]

да при построении графика хеш построить по y по пикселям и всё, один фиг он квантует данные для отрисовки.

[Aquahawk]

блин, реально и хеш не нужен, ниже уже указали как правильно, ступил

[RuGrof]

Здесь же простой пример

Плохой пример.

согласен с автором статьи, что если объем данных большой

То есть бинарный поиск будет быстрее чем i = Math.round(P/ (L / C)), где:

• i — индекс для svgData (начинается с 0)
• L — длинна графика
• С — Количество отрезков на графике
• P — координата курсора относительно начала графика

Опять же, если количество отрезков будет больше, чем количество пикселей, наглядность будет совсем хромать и придётся их группировать, чтоб хотя-бы отрезки по 1px получить.

[Deosis]

Ещё в статье не рассказано про интерполяционный поиск.
В нем надо строку

const middle = Math.floor((start + (end - start)/2);

заменить на

const middle = Math.round(start + (target - data[start].svgX) * (end - start)/ (data[end].svgX - data[start].svgX))

Если данные в массиве расположены более менее равномерно, то такой поиск будет эффективнее. В крайнем случае формула вырождается в ту, что привели выше.

[siziyman]

Простите, а что в материале (несмотря на то, что это перевод — я бы даже сказал особенно учитывая то, что это перевод) заслуживает публикации на хабре? Тема базовая, я бы даже сказал, примитивная, уровень подачи, объяснения материала тоже не выделяется.

[merovinh]

Повторение — мать учения. Да, тема не сложная, согласен. Но думаю найдется достаточно людей, кому как и мне будет интересно вспомнить университетские знания.

[siziyman]

Для того, чтобы её вспомнить, есть множество аналогичных или более содержательных материалов.

[Poccomaxa_zt]

Вы всегда можете помочь читателям Хабра и опубликовать эти более полезные статьи. Либо же оставить ссылки на оригиналы для заинтересовавшихся людей.
Автору же в любом случае спасибо за потраченное время и приложенный труд.

[Movebytes]

Фильтратор статтей свое дело знает. Наверное это ООООЧЕНЬ страшно увидеть статью о бинароном поиске в своей ленте. Бедьняжечка

[siziyman]

Получить два комментария, которые сводятся к «да пошёл ты», от профилей с нулевой кармой и историей, и которые подписаны только на компанию, в блоге которой раньше публиковался автор этого поста — это, кхм, заставляет задуматься.

[siziyman]

Не спорю, у меня профиль здесь тоже тухлый, но чуть более живой на ГТ. Плюс я по нику в сети ищусь легко. И я не подписан на одну компанию. :)

[bfDeveloper]

Извините, но пост ужасен. Во-первых, с такими темпами у нас будут статьи «2+2 на JavaScript». Во-вторых, выкладывать код не самого хорошего качества в обучающей статье — плохо.
Я молчу про однобуквенные переменные с комментом (это же канон плохого коментария, от которого надо избавляться). Но этот код не будет работать с пустым массивом — банально зациклится. Это одна из ошибок новичка, такое студенты на первом курсе пишут и больше такого не делают. Зачем такое публиковать?
Кроме того, 100 лет как принянто диапазоны делать открытыми справа, то есть не включать правую границу и не писать уродливое data.length -1. В случае пустого получаем -1, а что это за индекс?
Ну и в качестве придирки. Плохим тоном, хотя и без последствий в js, является вычисление среднего (a+b)/2. Давно придумали писать a + (b-a)/2, чтобы не иметь переполнений. Да, в js всё double и проблем не будет, но ведь потом так напишут на чём-нибудь ближе к железу.

[bfDeveloper]

И ещё, если мы говорим о производительности, то что в коде делает рекурсия? Итеративный вариант точно будет быстрее, да ещё и от переполнения стека защищён. Тут конечно можно сделать через оптимизацию хвостовой рекурсии, но для этого надо код переписать. Так как есть, ни один компилятор не осилит. Да и не думаю, что хоть один движок js это вообще делает.

[merovinh]

Спасибо за конструктив, сделал несколько исправлений.

[kahi4]

Это гениально — сравнивать перебор (сложность O(n)) и бинарный поиск (O(logn)).

Если объем данных небольшой, рекурсия может быть медленнее, чем цикл for. При тестировании на jsperf с 10 элементами, рекурсивная функция в среднем на 3% медленнее, чем цикл for. Однако при количестве элементов в 10 000, цикл for на 72% медленнее, чем рекурсивная функция. Это означает, что рекурсия практически в два раза быстрее, чем цикл for, и это огромная экономия времени!

Голословненько. Где пруфы?

А бинарным поиском без рекурсии, через while слабо? А вместо монстра Math.floor((a+b)/2) битовый сдвиг, видимо, для нердов и никому уже не нужно.

[impfromliga]

Ничего не буду объяснять, нет времени, достал из своих загашников, в апи все и так написано, просто оставлю здесь этот лаконичный, быстрый, надежный, универсально расширяемый вариант:

//lib
function bsrc(arr, search){
var toValue = arguments[2] || search.toValue || (f=>f);
search = toValue(search);
for(var x1=0, mid, x2=arr.length; x1 < x2;){
mid = x2+x1-1>>1;
if(toValue(arr[mid]) > search) x2=mid;
else x1=mid+1;
}
return (x1%=arr.length) && toValue(arr[x1-=1])==search ? x1:-1;
}

//prepare 1:
var arr = [3, 24, 32, 35, 38, 45, 46, 49, 52, 52, 69, 71, 75, 77, 78, 89, 89, 90, 96, 99];
//usage 1:
bsrc(arr,35);

//prepare 2:
var arr = [3, 24, 32, 35, 38, 45, 46, 49, 52, 52, 69, 71, 75, 77, 78, 89, 89, 90, 96, 99];
arr.bsrc = bsrc.bind(this,arr);
//usage 2:
arr.bsrc(38);

//prepare 3:
var arr = [{key:8, val:3}, {key:10, val:24}, {key:15, val:32}, {key:21, val:35}, {key:39, val:38}];
arr.bsrc = bsrc.bind(this,arr);
//usage 3:
arr.bsrc({val:32},f=>f.val);
arr.bsrc({key:21},f=>f.key);