Search in Rotated Sorted Array

Introduction

Binary Search works perfectly on sorted arrays. But what happens if the array is rotated(first element is at last)?

This problem challenges us to adapt binary search to work even when the array is not fully sorted in the usual way.

Problem Statement

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

Your task is to find the index of a given target.

• If found then return index
• If not found then return -1
• Time complexity must be O(log n)

Example

Input:

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

Output:

4

What is a Rotated Array?

Original sorted array:

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

After rotation:

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

Key Insight

At any point:

• One half of the array is always sorted

We use this property to decide where to search.

Approach

1. Use Binary Search
2. Find middle element
3. Check which half is sorted
4. Decide where the target lies

Steps

• If nums[left] <= nums[mid] then Left half is sorted

  • If target lies in this range then search left
  • Else...search right

• Else...Right half is sorted

  • If target lies there then search right
  • Else...search left

Python Implementation

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

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

        if nums[mid] == target:
            return mid

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

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

    return -1

Step-by-Step Example

For:

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

• mid = 7 then left is sorted but target not here so move right
• mid = 1 then right is sorted but target is not here so move left
• mid = 0 target is found

---

Key Points

• Always one half is sorted
• Modify binary search logic
• Avoid linear search (O(n))
• Very common interview problem

Conclusion

This problem teaches how to adapt binary search for modified conditions. By identifying the sorted half at every step we can still achieve efficient searching even in rotated arrays.

Mastering this pattern is crucial for solving many advanced search problems.