Выбор ответа Middle Бинарный поиск спрашивают часто обновлено
Бесконечный цикл в бинпоиске
Вопрос
Функция ищет первый индекс, где arr[i] >= x. На каком входе она зациклится?
function lowerBound(arr, x) {
let l = 0, r = arr.length;
while (l < r) {
const mid = (l + r) >> 1;
if (arr[mid] < x) l = mid;
else r = mid;
}
return l;
}
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: arr = [1, 3], x = 3. При l = 0, r = 1 (arr = [1, 3], x = 3): mid = 0, arr[0] < 3, и l = mid снова 0.
Варианты ответа
arr = [1, 3],x = 3правильный ответarr = [],x = 1arr = [5],x = 1- Никогда не зацикливается
Разбор
При l = 0, r = 1 (arr = [1, 3], x = 3): mid = 0, arr[0] < 3, и l = mid снова 0. Цикл вечный. Нужно l = mid + 1: элемент mid уже точно не подходит.
- Пустой массив:
r = 0, цикл не начнётся. [5],x = 1:l === rсразу.- Зацикливание есть, как показано выше.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.