Search in a Rotated Sorted Array Using Binary Search

Introduction

The Search in a Rotated Sorted Array problem is one of the most frequently asked DSA interview questions related to binary search. Many learners find it confusing because the array looks unsorted at first glance.

In simple words, this problem asks you to search for a number in an array that was originally sorted but then rotated.

This article explains the problem in simple, human-friendly language, with real-world meaning, step-by-step logic, and the exact binary search approach interviewers expect.

Real-World Meaning of Rotated Sorted Array

Imagine a sorted book shelf:

1 2 3 4 5 6 7

Now someone rotates it by picking a middle part and moving it to the front:

4 5 6 7 1 2 3

The order inside each part is still sorted, but the whole shelf looks mixed.

This is exactly what a rotated sorted array looks like.

What is a Rotated Sorted Array?

A rotated sorted array is:

• An array that was originally sorted

• Rotated at some unknown pivot

Example

Original: [1, 2, 3, 4, 5, 6, 7]
Rotated:  [4, 5, 6, 7, 1, 2, 3]

Problem Statement

You are given:

• A rotated sorted array with unique elements

• A target value

Your task is to return the index of the target if it exists, otherwise return -1.

Example

Array:  [4, 5, 6, 7, 0, 1, 2]
Target: 0
Output: 4

Before vs After Understanding

Linear Search (Before)

• Check each element one by one

• Works, but slow

Binary Search (After)

• Identify which half is sorted

• Decide where the target can exist

• Reduce search space by half

Why Normal Binary Search Does Not Work Directly

Normal binary search assumes:

• Entire array is sorted

But here:

• Only one half is sorted at any time

So we slightly modify the binary search logic.

What Interviewers Are Actually Testing

Interviewers want to see:

• Can you detect sorted halves?

• Can you adapt binary search logic?

• Can you reason about search space?

This problem tests binary search mastery.

Key Idea (Very Simple)

At any point:

• One half of the array is always sorted

• Check if target lies in that sorted half

• Move search space accordingly

Step-by-Step Logic

1. Set low = 0, high = n - 1

2. Find mid

3. If arr[mid] == target, return mid

4. Check which half is sorted:

   • If left half is sorted

     • If target lies in left half, move left

     • Else move right

   • If right half is sorted

     • If target lies in right half, move right

     • Else move left

5. Repeat until found or search space is empty

Dry Run Example

Array: [4, 5, 6, 7, 0, 1, 2], Target = 0

low	high	mid	sorted half	move
0	6	3	left	right
4	6	5	right	left
4	4	4	-	found

Answer index = 4

One-Line Logic Before Code

Always move toward the half where the target can logically exist.

Code Implementation (C++)

int search(vector<int>& nums, int target) {
    int low = 0, high = nums.size() - 1;

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

        if (nums[low] <= nums[mid]) {
            if (nums[low] <= target && target < nums[mid])
                high = mid - 1;
            else
                low = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[high])
                low = mid + 1;
            else
                high = mid - 1;
        }
    }
    return -1;
}

Common Beginner Mistakes

• Forgetting one half is always sorted

• Applying normal binary search blindly

• Wrong boundary conditions

Time and Space Complexity

• Time Complexity: O(log n)

• Space Complexity: O(1)

Easy Summary (Explain Like I’m 10)

Even though the array looks mixed, part of it is always sorted. If you look carefully at the middle and see which side is in order, you can decide where the number could be and ignore the rest.

Summary

Searching in a rotated sorted array using binary search is a powerful interview problem that tests logical reasoning and adaptability. By identifying the sorted half at every step and narrowing the search space correctly, you can find the target efficiently in logarithmic time. Mastering this problem strengthens your overall binary search problem-solving skills.