Problem Statement in English

You’re given an integer array nums sorted in non-decreasing order (not necessarily with distinct values). Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed).

Return true if target is in nums, or false if it is not.

Approach

Although it seems intimidating, we can still use a very slightly modified binary search to solve this problem.

We need to identify if the left half or right half is sorted, but one half is guaranteed to be sorted.

Since we don’t particularly know which half the target is in, if at all, we deal with something we can actually be sure about: check if the target is in the sorted half. If it is, we can narrow our search to that half. If not, we can narrow our search to the other unsorted half, and repeat the exact same process.

In order to find the sorted half, we can compare the leftmost and middle elements. If the leftmost element is less than or equal to the middle element, then the left half is sorted. Otherwise, the right half is sorted.

There’s also a special case we need to handle: if the leftmost, middle, and rightmost elements are all equal, we can’t determine which half is sorted. In this case, we can simply move the left pointer one step to the right and the right pointer one step to the left, effectively narrowing our search space.

And we’re done!

Solution in Python


class Solution:
    def search(self, nums: list[int], target: int) -> bool:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target:
                return True

            # Handle duplicate edge case: unable to determine sorted half
            if nums[left] == nums[mid] == nums[right]:
                left += 1
                right -= 1
            # Left half is sorted
            elif nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            # Right half is sorted
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return False

Complexity

  • Time: $O(\log n)$
    Since we are using a binary search approach, the time complexity is logarithmic with respect to the number of elements in the array.

  • Space: $O(1)$
    Since we are using a constant amount of extra space (only a few variables), the space complexity is constant.

And we are done.