LeetCode 81: Search in Rotated Sorted Array II

Time: $\mathcal{O}(\lg{n})$ , space: $\mathcal{O}(1)$ .

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        n = len(nums)
        lo, hi = 0, n-1
        while lo <= hi:
            mid = (lo + hi)//2
            if nums[mid] == target:
                return True
            
            # As long as nums[lo] != nums[hi]
            # we can use same approach as if all
            # numbers between lo and hi were distinct
            if nums[lo] == nums[hi]:
                lo += 1
                continue
            
            if nums[mid] >= nums[lo]: # mid is on the left of break
                if target >= nums[lo] and target < nums[mid]:
                    hi = mid-1
                else:
                    lo = mid+1
            else:
                if target > nums[mid] and target <= nums[hi]:
                    lo = mid+1
                else:
                    hi = mid-1

        return False

If all numbers were distinct, we could find which side of pivot $\texttt{mid}$ is on by comparing $\texttt{nums[mid]}$ with $\texttt{nums[lo]}$ as below. Here, with duplicates allowed, we reduce the problem to the all-distinct case by making sure $\texttt{nums[lo]} \neq \texttt{nums[hi]}$ .