📌 Задача. Поиск в повернутом отсортированном массиве

Условие задачи: дан массив, сдвинутый относительно опорного элемента, который неизвестен ( массив после сдвига относительно опорного элемента имеет следующий вид: [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]])

Массив [0,1,2,4,5,6,7], имея опорный элемент 3, будет выглядеть следующим образом: [4,5,6,7,0,1,2].

Необходимо осуществить поиск целевого элемента в сдвинутом массиве, определив его индекс, или же вывести -1 при его отсутствии.

Решение должно быть за O(log n) по времени.

Пример:

Ввод: nums = [4,5,6,7,0,1,2], target = 0

Вывод: 4

Ввод: nums = [4,5,6,7,0,1,2], target = 3

Вывод: -1

Решение:

class Solution:
def search(self, nums: List[int], target: int) -> int:
if target in nums :
return nums.index(target)
else :
return -1

Пишите свое мнение в комментариях👇

@python_job_interview