Выбор ответа Senior Задачи на Kotlin обновлено
binarySearch при повторяющихся элементах
Вопрос
Что вернёт listOf(1, 3, 3, 3, 5).binarySearch(3)?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Один из индексов 1, 2 или 3, без гарантии. Стандартный бинарный поиск гарантирует только, что вернёт индекс найденного элемента, но при повторах не уточняет какого.
Варианты ответа
- Всегда 1, первый индекс тройки
- Один из индексов 1, 2 или 3, без гарантииправильный ответ
- Всегда 3, последний индекс тройки
-1, потому что значение повторяется
Разбор
Стандартный бинарный поиск гарантирует только, что вернёт индекс найденного элемента, но при повторах не уточняет какого. Для нижней и верхней границы (первое вхождение, количество элементов <= x) пишут свой поиск с инвариантом lo/hi. Отрицательное значение возвращается, только если элемента нет: -(точка вставки) - 1.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.