Search in Rotated Sorted Array

Introduction

Binary Search works efficiently on sorted arrays.
But what if the array is rotated?

This problem teaches how to apply binary search even when the array is not fully sorted but partially sorted.

Problem Statement

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

Task:
Find the index of a target element.
If not found, return -1.

Constraint:

• Time complexity must be O(log n)

Examples

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

Example 3:
Input: nums = [1], target = 0
Output: -1

Intuition

Even though the array is rotated, one half is always sorted.

So:

• Check which half is sorted
• Decide where the target lies
• Apply binary search accordingly

Approach

Algorithm Steps

• Initialize:

  • low = 0, high = n - 1

• While low <= high:

  • Find mid: mid = (low + high) // 2
  • If nums[mid] == target → return mid

• Check sorted half:

  • If left half is sorted (nums[low] <= nums[mid]):
    • If target lies in left → search left
    • Else → search right
  • Else right half is sorted:
    • If target lies in right → search right
    • Else → search left

Code (Python)

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

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

        if nums[mid] == target:
            return mid

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

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

    return -1

Step-by-Step Explanation

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

• mid = 7 → left sorted
• target not in left → go right
• mid = 1 → found

Complexity Analysis

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

Conclusion

This problem is a powerful extension of binary search and is frequently asked in technical interviews.