Search in Rotated Sorted Array

Search in Rotated Sorted Array
Problem Statement

We are given a sorted array that has been rotated at some unknown index.
We need to find the index of a target element in O(log n) time.

If the target is not found, return -1.

Example
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Understanding Rotated Sorted Array

A rotated array looks like this:

Original Sorted Array:
[0,1,2,4,5,6,7]

After Rotation:
[4,5,6,7,0,1,2]

Observation:

One half of the array is always sorted

We use Binary Search logic to decide which half to search

Approach: Modified Binary Search
Idea

At every step:

Find mid

Check which half is sorted

Check if target lies in that sorted half

Move left or right accordingly

Steps Algorithm

Set low = 0, high = n-1

Find mid

If nums[mid] == target → return mid

If left half is sorted:

If target in left range → search left

Else → search right

Else right half is sorted:

If target in right range → search right

Else → search left

Repeat

Python Code
def search(nums, target):
low = 0
high = len(nums) - 1

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

    if nums[mid] == target:
        return mid

    # Left half sorted
    if nums[low] <= nums[mid]:
        if nums[low] <= target < nums[mid]:
            high = mid - 1
        else:
            low = mid + 1

    # Right half sorted
    else:
        if nums[mid] < target <= nums[high]:
            low = mid + 1
        else:
            high = mid - 1

return -1

nums = [4,5,6,7,0,1,2]
print(search(nums, 0))
Example Walkthrough
nums = [4,5,6,7,0,1,2]
target = 0
Low Mid High Sorted Part
0 3 6 Left sorted
4 5 6 Right sorted
Found at index 4

Complexity Analysis
Type Complexity
Time O(log n)
Space O(1)

This works because we eliminate half of the array each time.

Key Concepts Learned

Binary Search

Rotated Sorted Array

Searching in partially sorted array

Divide and conquer

Logarithmic time complexity

Conclusion

To search in a rotated sorted array:

Use Modified Binary Search

Identify which half is sorted

Check if target lies in sorted half