Search in Rotated Sorted Array DSA Solution - Study Chapter | QuizMaker

Search in Rotated Sorted Array explained with brute force, optimized rotated binary search, dry run, edge cases, complexity, and Python, C++, Java code.

Read: 12m
Type: Chapter
Access: Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 3: Binary Search

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.

Input	Target	Output
`[4,5,6,7,0,1,2]`	`0`	`4`
`[4,5,6,7,0,1,2]`	`3`	`-1`

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

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = (int)nums.size() - 1;

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

            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
};

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

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

            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
}

Sample Dry Run

left	right	mid	Observation	Action
0	6	3	Left side `[4,5,6,7]` is sorted, target 0 is not inside	Move left to 4
4	6	5	Left side `[0,1]` is sorted, target 0 is inside	Move right to 4
4	4	4	`nums[4] = 0`	Return 4

Complexity

Measure	Value	Reason
Time	O(log n)	One half is discarded each step.
Space	O(1)	Only index boundaries are stored.

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

Why does one half stay sorted?

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

What if duplicates exist?

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

What is the core pattern?

Binary search with sorted-half detection.