У меня следующий вопрос: рассмотрим массив различных чисел, отсортированных в порядке возрастания.Массив был повернут (по часовой стрелке) k раз.Учитывая такой массив, найдите значение k.
Я понимаю, что это хорошо известный вопрос, который был задан (и что на это есть ответы в Интернете), но мой вопрос не оРешение этой проблемы.
У меня была эта проблема в тесте, и я сказал, что решение этой проблемы может быть: найти первое число, которое меньше, чем у предшественников в массиве.Способ, который я выбрал, это увеличивать прыжки с силой 2 от начала массива.Я продемонстрирую: предположим, что k = 29, тогда я проверю 2,4,8,16,32.значение на месте 32 меньше, но не первое.затем я прыгну с места 17 (прыжки описаны выше): 17, 19, 23, 31. место 31 меньше, но не первое.следующий этап проверки: 24,26,30.на этот раз значение в месте 30 меньше и сначала верните 30-1.(Я могу написать это как алгоритм, но я думаю, что это продемонстрирует ясность мышления)
Я думаю, что это будет работать рекурсивно и, безусловно, даст мне ответ.Мой лектор сказал мне, что я был неправ.Итак, мой вопрос: я действительно не прав?во-вторых, я изо всех сил пытался найти время работы алгоритма.Я знаю, что первый прогон - больше всего O (logk), а другие прогоны (на подмассивах) меньше, но какова сумма тогда в худшем случае.Я говорю вам правду, я сначала подумал, что все равно будет o (logk), но сейчас я не совсем уверен в этом.
спасибо.