Бинарный поиск

[nameisBegemot]

Найти число бинарным поиском это конечно замечательно. Но в реальности чаще возникает другая задача - как найти период некоторых чисел, которые старше некоторого порогового значения. Например, из массива в 100 чисел найти индексы ячеек от 75.

Прямо в лоб поделить массив пополам мало. Нужно найти границы интервалов. Код несложный, но интереснее поиска отдельного числа.

А да, поиск интервалов все тот же бинарный поиск.

[Deosis]

const mid = Math.floor((left + right) / 2);

Знаменитый баг, который ломает бинарный поиск на больших массивах.

[mayorovp]

Конкретно Math.floor ничего не ломает, оно просто медленное.

Чтобы его сломать, нужны индексы более . Я не верю в такие массивы на Javascript.

[Neoldian]

Что забавно, почти в каждой статье или заметке по бинарному поиску пишут именно так) Что бы не ломать потом голову лучше писать a + (b-a)/2 , и не будет никакого переполнения.

[mayorovp]

Если написать  a + (b-a)/2 - может получиться нецелый индекс. Числа-то в Javascript вещественные...

[Neoldian]

Приведение к целому конечно необходимо, я про то что именно выражение лучше писать a + (b-a)/2, в js оно как раз без последствий. Статья то образовательная, и не хочется чтобы у кого то, кто перепишет на более близких к железу языках как (a+b)/2, была головная боль с overflow)

[Metotron0]

Мне помнится, что в книге «Грокаем алгоритмы» бинарный поиск расписан очень подробно. Неужели была необходимость в ещё одном объяснении, а не в ссылке на страницу книги?

Собственно, поэтому я и не пишу статьи на хабр: они будут состоять только из ссылки.

[Semigradsky]

Книгу купить ещё надо

[Metotron0]

Не подумал

[qss53770]

Да про бин поиск везде написано куча читай не хочу, автор недавно видимо сделал это открытие и думает дай ка напишу на хбре про стандартную задачу и стандартный алгоритм

[nronnie]

Посмотрим последний элемент массива one. 49 больше, чем 87? Нет.

@Open-JS, у вас в примере кода "49" в массиве куда-то потерялось - поправьте.