Search in Rotated Sorted Array: Rotated search Pattern

Learning Outcome

After this lesson, you should be able to adapt binary search when the array is sorted but rotated around a pivot.

Problem Statement

Given a rotated sorted array with distinct values and a target, return the target index or -1 if it is not present.

Brute Force Approach

Scan every index and return the one matching the target. This works, but costs O(n).

Optimized Approach

At every step, at least one side of the current range is sorted. Check whether the left side [left, mid] is sorted. If it is, decide whether the target lies inside that sorted range. Otherwise, the right side must be sorted and the same decision applies there.

Exact Pseudocode

left = 0
right = length(nums) - 1
while left <= right:
  mid = left + (right - left) // 2
  if nums[mid] == target:
    return mid
  if nums[left] <= nums[mid]:
    if nums[left] <= target and target < nums[mid]:
      right = mid - 1
    else:
      left = mid + 1
  else:
    if nums[mid] < target and target <= nums[right]:
      left = mid + 1
    else:
      right = mid - 1
return -1
  

Reference Code

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

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid

            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1
  

Sample Dry Run

Complexity

Edge Cases

• Array is not rotated.
• Target is at the pivot.
• Single-element array.

Interview Checklist

• Identify which half is sorted.
• Check whether target lies inside the sorted half.
• Use inclusive boundaries carefully.

FAQs

A rotated sorted array has one pivot, so in any range at least one side around the middle remains sorted.

The classic version assumes distinct values. Duplicates need extra handling because sorted-half detection can become ambiguous.

Binary search with sorted-half detection.