Участник:Ковальков Антон М05-903б/Search in Rotated Sorted Array

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/search-in-rotated-sorted-array/

Python3

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def foo(l, m, r):
            if l < 0 or m < 0 or r < 0:
                return -1
            if  nums[l] == target:
                return l
            if nums[r] == target:
                return r
            if nums[m] == target:
                return m
            if l == m or l == r or r == m:
                return -1
 
 
            if nums[r] < nums[l] < nums[m] or nums[l] < nums[m] < nums[r]:
                if nums[l] < target < nums[m]:
                    return foo(l, (l+m)//2, m)
                else:
                    return foo(m, (r+m)//2, r)
 
            elif nums[m] < nums[r] < nums[l]:
                if nums[m] < target < nums[r]:
                    return foo(m, (r+m)//2, r)
                else: 
                     return foo(l, (l+m)//2, m)
 
            return -1
 
        return foo(0, (len(nums)-1)//2, len(nums)-1)