Solutions

1. Brute Force

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        return target in nums

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

2. Binary Search

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        l, r = 0, len(nums) - 1
        while l <= r:
            m = l + (r - l) // 2
            if nums[m] == target:
                return True

            if nums[l] < nums[m]:  # Left portion
                if nums[l] <= target < nums[m]:
                    r = m - 1
                else:
                    l = m + 1
            elif nums[l] > nums[m]:  # Right portion
                if nums[m] < target <= nums[r]:
                    l = m + 1
                else:
                    r = m - 1
            else:
                l += 1

        return False

Time & Space Complexity

Time complexity: $O(\log n)$ in average case, $O(n)$ in worst case.
Space complexity: $O(1)$