ROTATED SORTED ARRAY

How I Understood Search in a Rotated Sorted Array (LeetCode 33)
When I first saw this problem, it looked tricky because the array is rotated, so normal binary search won’t always work.
After analyzing it, I realized the key is to identify which half is sorted in each step.

Problem
Given a rotated sorted array nums and a target value, return its index if found, else return -1.
A rotated array means it was originally sorted but then shifted at some pivot.
Example:
Python
nums = [4,5,6,7,0,1,2]
target = 0

Output: 4

Python
nums = [4,5,6,7,0,1,2]
target = 3

Output: -1

What I Noticed
Instead of trying linear search, I noticed:
Even after rotation, at least one half of the array is sorted
We can use binary search logic on the sorted half
Check if the target is in that half
If yes, search there; if not, search the other half
This keeps O(log n) efficiency.

What Helped Me
Breaking it into three key steps clarified the approach:
Binary search loop: low <= high
Check sorted half:
If nums[low] <= nums[mid], left half is sorted
Else, right half is sorted
Decide which half to continue:
If target lies within sorted half → adjust low or high
Else → search the other half
Repeat until the target is found or the search space is empty.

Code (Python)
Python
from typing import List

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

    while low <= high:
        mid = low + (high - low) // 2

        if nums[mid] == target:
            return mid

        # Step 1: Identify which half is sorted
        if nums[low] <= nums[mid]:
            # Left half is sorted
            if nums[low] <= target < nums[mid]:
                high = mid - 1  # Target is in left half
            else:
                low = mid + 1   # Target is in right half
        else:
            # Right half is sorted
            if nums[mid] < target <= nums[high]:
                low = mid + 1   # Target is in right half
            else:
                high = mid - 1  # Target is in left half

    return -1

📝 Example Usage
Python
nums = [4,5,6,7,0,1,2]
target = 0
solution = Solution()
print(solution.search(nums, target))
Output:
Plain text
4

** Complexity**
Time: O(log n) — binary search with rotation logic
Space: O(1) — constant extra space

What I Learned
This problem highlights how binary search can be adapted:
Always check which side is sorted
Decide the search space based on target location
Avoid linear search even in rotated arrays

Final Thought
At first, I thought rotation makes binary search impossible.
Once I realized:
“One half is always sorted — use that”
…it became intuitive and efficient.
This is a classic example of modifying binary search for special array structures.