binary search - leetcode 33. Search in Rotated Sorted Array

1. Question

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

2. Solution

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
        

3. Test case

    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()

4. Explanation

find the rotate position by binary search.

search in the left part of rotate position by binary search.

search in the right part of rotate position by binary search.

5. Basics of binary search

mid = left + right + 1//2 : this can handle those special situation related with odd or even lists.

left = mid + 1 & right = mid - 1 : this can make pointer move forward.

i = bisect.left(list, target, low, high) : search in [low, high) , use "i != len(nums) and nums[i] != target "to find the index.