Как решить задачу на Поиск граничного элемента?

Question

[Serufim]

Есть следующая задача, если написать алгоритм для нахождения F с скоростью lg N не составляет никакого труда и все решается обычным бинарным поиском, то алгоритм способный решить такую задачу за lg F я ни как не могу придумать, как и алгоритм который бы решал задачу за 2√N. Мне не нужен код, просто подскажите пожалуйста с чего начать и как подступиться к реализации этих алгоритмов

===== Сама задача =====

Имеется здание из N этажей и неограниченное количество яиц. Будет считать, что яйцо разбивается, если оно падает с этажа F или выше. Если яйцо падает с этажа ниже, то оно остается целым и может быть использовано повторно. Требуется реализовать алгоритм поиска значения F при условии, что можно разбить примерно lgN яиц и выполнить примерно lg N попыток.

Модернизируйте алгоритм поиска таким образом, чтобы количество попыток было примерно lgF при условии, что N много больше F.

Дополнительно. Решите задачу при условии, что имеется всего два яйца. Реализуйте алгоритм поиска F с количеством попыток, не превышающем 2(√N). Попробуйте уменьшить стоимость поиска до C(√N) для некоторой константы C.

Answer 1

[youngmysteriouslight]

Если испытывать поочерёдно этажи 1, 2, 4, 8, ..., 2^K, 2^{K+1} до тех пор, пока яйцо не разобъётся, а потом уточнить значение F из промежутка 2^K..2^{K+1} бинарным поиском, количество попыток будет (2 lgF). Если слово «примерно» допускает коэффициент 2, то алгоритм подходит.

Если в распоряжении только одно яйцо, то нет никакого другого способа, кроме как идти снизу вверх подряд, O(N).
Если есть два яйца, первым можно идти с более грубым шагом A[1], A[2], A[3], ..., A[K], A[K+1], а вторым уточнять точное значение F из A[K]..A[K+1]. Причём шаг A[K+1]-A[K] определяет количество попыток для второго яйца, то есть суммарное количество попыток будет K+A[K+1]-A[K]. Осталось определить вид последовательности A[i], чтобы K+A[K+1]-A[K]=O(√A[K+1]).
Собственно, чтобы достичь 2(√N), нужно первым яйцом идти с шагом (√N), то есть 1, 1+(√N), 1+2(√N), 1+3(√N), ..., а когда разобъётся на 1+(K+1)(√N), идти вторым подряд с этажа 2+K(√N).

Comments

[Serufim]

Большое спасибо за ваш большой и развернутый ответ

Answer 2

[Денис Загаевский]

Решение в общем виде https://habrahabr.ru/post/211200/