Search in Rotated Sorted Array Using Binary Search

Introduction

The Search in Rotated Sorted Array problem is a very common DSA interview question. It primarily tests your understanding of Binary Search and how to adapt it when the array is not fully sorted.

In this problem, the array was originally sorted and then rotated by an unknown amount. Even after rotation, we can still search efficiently using a smart version of binary search.

What is a Rotated Sorted Array?

A rotated sorted array is an array that was originally sorted in ascending order but then rotated.

Example

Original sorted array:

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

After rotation:

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

The order is broken at one point, but one half of the array is always sorted.

Problem Statement

You are given:

A rotated sorted array
A target element

Your task is to find the index of the target element. If the element is not present, return -1.

Example

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

Why Normal Binary Search Does Not Work

Normal binary search works only when the array is fully sorted.

In a rotated sorted array:

One part is sorted
The other part is not

So we need to identify the sorted half first, then decide where to search.

Optimized Approach Using Modified Binary Search

We use a modified binary search approach that works in O(log n) time.

Key Idea

At any point:

Either the left half is sorted
Or the right half is sorted

We check which half is sorted and whether the target lies in that half.

Step-by-Step Explanation

Steps:

Initialize low and high
Find mid
If nums[mid] equals target, return mid
Check which half is sorted
Decide whether to move left or right
Repeat until found or search space ends

Dry Run Example

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

Low	Mid	High	Action
0	3	6	Left half sorted, target not there
4	5	6	Right half sorted
4	4	5	Target found

Final Answer = Index 4

Code Implementation

C++ Code

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 (target >= nums[low] && target < nums[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        else {
            if (target > nums[mid] && target <= nums[high])
                low = mid + 1;
            else
                high = mid - 1;
        }
    }
    return -1;
}

Java Code

public int search(int[] nums, int target) {
    int low = 0, high = nums.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (nums[mid] == target)
            return mid;

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

Python Code

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

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

        if nums[mid] == target:
            return mid

        if nums[low] <= nums[mid]:
            if nums[low] <= target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:
            if nums[mid] < target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1

    return -1

Time and Space Complexity

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

This is as efficient as standard binary search.

Edge Cases to Consider

Array with only one element
Target not present
No rotation (fully sorted array)

Always test these cases.

Common Interview Variations

Find minimum element in rotated sorted array
Search with duplicate elements
Count number of rotations

These variations are also based on binary search logic.

Summary

The Search in Rotated Sorted Array problem is a classic example of how binary search can be adapted to handle special cases. By identifying which half of the array is sorted at each step, we can still search efficiently in logarithmic time. Understanding this logic is very important for coding interviews and builds strong confidence in binary search-based problems.