10,2 тыс подписчиков
📌 Задача. Поиск в повернутом отсортированном массиве
Условие задачи: дан массив, сдвинутый относительно опорного элемента, который неизвестен ( массив после сдвига относительно опорного элемента имеет следующий вид: [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
Пишите свое мнение в комментариях👇
Около минуты
4 мая 2023
429 читали