У Пети был массив целых чисел, состоящий из уникальных элементов и отсортированный по возрастанию. Его друг Вася, когда увидел массив, начал завидовать Пете и решил циклически сдвинуть исходный массив на k позиций. Другими словами, изначальный массив nums теперь имеет вид
[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
Дан массив nums (уже сдвинутый) и число target. Нужно за O(logN) найти индекс числа target в nums, или вернуть -1, если его нет.
Решение
Применим два бинарных поиска
Сначала найдем величину сдвига k: это достаточно просто сделать, сравниваем средний элемент с самым правым. Если средний больше, то точка сдвига находится правее, иначе левее и таким образом найдем k
Далее применим также бинарный поиск на всем массиве для нахождения индекса target.
Теперь, когда мы знаем наш сдвиг k, нам просто нужно изменить наше среднее значение следующим образом: currm = (m + k) % N. И задача решена
Два бинарных поиска: O(2logN) = O(logN)
@algoses