Search in Rotated Sorted Array

Problem Summary

• You are given an integer array nums that was originally sorted in ascending order
• Its rotated now at an unknown index
• Your task is to find the target in this array in $O(logn)$

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Previously sorted array
• $O(logn)$

Approach Taken

(Step-by-step logic or pseudocode before coding.)

• Good explanation

Why This Works

(Explain the core reason the solution is correct.)

• This approach works because in a rotated sorted array, at least one half (from l to m or from m to r) will always be monotonically increasing. By identifying the sorted half, we can efficiently determine if the target lies within that sorted range. If it does, we narrow our search to that half. If not, the target must be in the other (unsorted) half, and we continue the binary search there. This effectively reduces the search space by half in each iteration, maintaining the  time complexity.

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Binary Search
• Array

Time & Space Complexity

• Time: $O(logn)$ → Reason: Doing a Binary Search
• Space: $O(1)$ → Reason: Input isn't stored

Code

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1

        while l <= r:
            m = (l + r) // 2
            left = nums[l]
            right = nums[r]
            mid = nums[m]

            if target == mid:
                return m

            if left <= mid: #left is sorted
                if left <= target <= mid:
                    r = m - 1
                else:
                    l = m + 1
            else: # right is sorted
                if mid <= target <= right:
                    l = m + 1
                else:
                    r = m - 1
        return -1