binary search - leetcode 33. Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        def find_rotate_position(nums, l, r):
            mid = r-l+1
            while l <= r:
                if nums[l] > nums[r]:
                    mid = (l+r+1)//2
                    if nums[l] < nums[mid]:
                        l = mid + 1
                    else:
                        r = mid -1
                else:
                    return mid

        import bisect
        rotate_index = find_rotate_position(nums, 0, len(nums)-1)
        if rotate_index != len(nums) and nums[rotate_index] == target:
            return rotate_index
        else:
            i = bisect.bisect_left(nums, target, 0, rotate_index)
            if i != len(nums) and nums[i] == target:
                return i
            else:
                if rotate_index < len(nums):
                    i = bisect.bisect_left(nums, target, rotate_index+1, len(nums))
                    if i != len(nums) and nums[i] == target:
                        return i

        return -1
        

    def test_search():
		solution = Solution()
		
        nums = [4, 5, 6, 7, 0, 1, 2]
        target = 0
        res = solution.search(nums, target)
        assertEqual(res, 4)
        
        nums = [4, 5, 6, 7, 0, 1, 2]
        target = 3
        res = solution.search(nums, target)
        assertEqual(res, -1)
        
        nums = []
        target = 5
        res = solution.search(nums, target)
        assertEqual(res, -1)
        
        nums = [1]
        target = 0
        res = solution.search(nums, target)
        assertEqual(res, -1)

test_search()