📌 Задача. Поиск в повернутом отсортированном массиве
Условие задачи: дан массив, сдвинутый относительно опорного элемента, который неизвестен ( массив после сдвига относительно опорного элемента имеет следующий вид:
Массив
Необходимо осуществить поиск целевого элемента в сдвинутом массиве, определив его индекс, или же вывести -1 при его отсутствии.
Решение должно быть за O(log n) по времени.
Пример:
Ввод:
Вывод: 4
Ввод:
Вывод: -1
Решение:
@python_job_interview
Условие задачи: дан массив, сдвинутый относительно опорного элемента, который неизвестен ( массив после сдвига относительно опорного элемента имеет следующий вид:
[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