Выбор ответа Senior Бинарный поиск обновлено
Вычисление середины
Вопрос
Почему в C или Java пишут l + (r - l) / 2, а в JS часто пишут (l + r) >> 1?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: В Java l + r переполняет int, а в JS годится для индексов. В языках с 32-битным int сумма двух больших индексов переполняется.
Варианты ответа
- В JS
>>быстрее деления примерно в 100 раз, и это критично в цикле - Это одно и то же во всех языках, выбор только дело стиля кода
>>округляет вверх, поэтомуmidникогда не совпадёт сl- В Java
l + rпереполняет int, а в JS>>годится для индексовправильный ответ
Разбор
В языках с 32-битным int сумма двух больших индексов переполняется. В JS число это double, переполнения на индексах нет, а >> приводит к 32-битному целому и отбрасывает дробь, что подходит для индексов массива (они меньше 2³¹). Для произвольных больших чисел (бинпоиск по ответу до 10¹²) >> сломается, там нужен Math.floor((l + r) / 2).
- Разница в скорости несущественна.
- Поведение в языках разное, как объяснено.
>>для положительных округляет вниз.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.