Here is solutions for Search in Rotated Sorted Array

1. Understand the problem

• You’re given a rotated sorted array with distinct integers and a target value.

• Return index of target, or -1 if not found.

2. Clarify constraints (ask questions)

3. 📌 Key Idea

• At every step, at least one half is sorted.

• If the target is not in the sorted half, then it must be in the other half — so we discard the sorted one.

• If we only find 1 halve is sorted, another halve must be 1 element.

• We never need to “search in unsorted data” directly.

4. Brainstorm 2 - 3 ideas

4.1. Brute Force - O(N).

• Time: O(N).

• Space: O(1).

4.2. Binary search halves sorted - O(logN)

• From a rotated sorted array => You must be have 1 of halves are sorted.

• Quick check whether arr[left] <= target => belong to this halve, otherwise another halve: a sorted halve or only 1 element.

• Time: O(logN).

• Space: O(1)

5. Implement solutions

5.1. Brute force - O(N)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        for i in range(len(nums)):
            if nums[i] == target:
                return i
        return -1

• Time: O(N).

• Space: O(1)

5.2. Binary search halves sorted - O(logN)

class Solution:
    def search(self, nums, target):
        left, right = 0, len(nums) - 1

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

            if nums[mid] == target:
                return mid

            if nums[left] <= nums[mid]:  # Left side sorted
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:  # Right side sorted
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

• Time: O(logN).

• Space: O(1)