Search in Rotated Sorted Array

Problem Statement

You are given a sorted array that has been rotated at some unknown index.

Example:

Original sorted array:

[0,1,2,4,5,6,7]

After rotating left by 3:

[4,5,6,7,0,1,2]

Given:

Rotated sorted array nums
A target value target

Return:

The index of target if found
-1 if not found

⚡ Required Time Complexity: O(log n)

Example 1

Input:

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

Output:

4
Example 2

Input:

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

Output:

-1
Important Observation

Even though the array is rotated:

At least one half of the array is always sorted.
We can use Binary Search logic cleverly.
Key Idea

At every step:

Find mid
Check which half is sorted:
Left half sorted?
Right half sorted?
Check if target lies inside the sorted half.
Narrow the search space accordingly.

This ensures O(log n) complexity.

Step-by-Step Logic

Inside while loop:

Case 1: Left Half is Sorted

If:

nums[left] <= nums[mid]

Then:

If target lies between nums[left] and nums[mid]
→ Search left half
Else
→ Search right half
Case 2: Right Half is Sorted

Else:

If target lies between nums[mid] and nums[right]
→ Search right half
Else
→ Search left half
Python Implementation (O(log n))
class Solution:
def search(self, nums, target):
left = 0
right = len(nums) - 1

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

        # If target found
        if nums[mid] == target:
            return mid

        # Check if left half is sorted
        if nums[left] <= nums[mid]:

            # Target lies in left sorted half
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1

        # Otherwise right half is sorted
        else:

            # Target lies in right sorted half
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

Time and Space Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Why This Works

Even after rotation:

The array is divided into two halves.
One half will always remain sorted.
Binary search reduces search space by half each iteration.
Edge Cases Covered

Array size = 1
Target not present
No rotation (normal sorted array)
Rotation at last index