Problem statement

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

Solution

The idea is binary search here: divide array into 2 halves and understand, which part you should choose. Let us use dfs(beg, end) function, which will look inside region from beg to end. Then we check condition nums[mid] > nums[end] and if it is the case, we check where target is and decide to which half we need to go. Similar logic in another case. Look at examples [3,4,5,6,1,2] and [5,6,1,2,3,4] to understand what cases we can have.

Complexity

Time complexity is O(log n), space complexity is O(log n) as well because we use recursion.

Code

class Solution:
    def search(self, nums, target):
        def dfs(beg, end):
            if end - beg <= 1:
                if nums[beg] == target: return beg
                if nums[end] == target: return end
                return -1
            
            mid = (beg + end)//2
            if nums[mid] > nums[end]:   # eg. 3,4,5,6,1,2
                if nums[end] < target <= nums[mid]:
                    return dfs(beg, mid)
                else:
                    return dfs(mid, end)
            else: # eg. 5,6,1,2,3,4
                if nums[mid] < target <= nums[end]:
                    return dfs(mid, end)
                else:
                    return dfs(beg, mid)
    
        return dfs(0, len(nums) - 1)