Search in Rotated Sorted Array in DSA C++

Mental Model

We find a number in a sorted list that has been turned around at some point. We use a smart search that checks which part is sorted to decide where to look next.

Analogy: Imagine a circular train track with stations in order. The train stops at a random station and the order looks broken. To find a station, you check which side of the track is still in order and decide where to go next.

Original sorted array:
[1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> null

Rotated array example:
[4] -> [5] -> [6] -> [7] -> [1] -> [2] -> [3] -> null
↑ start here

Dry Run Walkthrough

Input: array: [4,5,6,7,0,1,2], target: 0

Goal: Find the index of target 0 in the rotated sorted array

Step 1: Set left=0, right=6, mid=(0+6)/2=3, check value at mid=7

[4] -> [5] -> [6] -> [7↑] -> [0] -> [1] -> [2] -> null

Why: We start by checking the middle element to decide which half to search next

Step 2: Left half [4..7] is sorted because 4 <= 7; target 0 is not in [4..7], so search right half

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2] -> null (search right half: indices 4 to 6)

Why: Since target is less than left value and less than mid, it must be in the unsorted right half

Step 3: Set left=4, right=6, mid=(4+6)/2=5, check value at mid=1

[4] -> [5] -> [6] -> [7] -> [0] -> [1↑] -> [2] -> null

Why: Check middle of right half to narrow down search

Step 4: Right half [1..2] is sorted; target 0 is less than 1, so search left half

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2] -> null (search left half: indices 4 to 4)

Why: Target is less than mid value, so it must be in left half

Step 5: Set left=4, right=4, mid=4, check value at mid=0

[4] -> [5] -> [6] -> [7] -> [0↑] -> [1] -> [2] -> null

Why: Check the last possible position

Step 6: Found target 0 at index 4

[4] -> [5] -> [6] -> [7] -> [0↑] -> [1] -> [2] -> null

Why: Target matches mid value, search ends

Result:

Final state: [4] -> [5] -> [6] -> [7] -> [0↑] -> [1] -> [2] -> null
Target 0 found at index 4

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

int searchInRotatedSortedArray(const vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid; // found target
        }
        // Check if left half is sorted
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1; // target in left half
            } else {
                left = mid + 1; // target in right half
            }
        } else { // right half is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1; // target in right half
            } else {
                right = mid - 1; // target in left half
            }
        }
    }
    return -1; // target not found
}

int main() {
    vector<int> nums = {4,5,6,7,0,1,2};
    int target = 0;
    int index = searchInRotatedSortedArray(nums, target);
    cout << "Target " << target << " found at index: " << index << endl;
    return 0;
}

int mid = left + (right - left) / 2;

calculate middle index to split search range

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

check if middle element is target

if (nums[left] <= nums[mid]) {

check if left half is sorted

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

decide to search left or right half based on target position

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

right half is sorted, decide search side accordingly

Output

Target 0 found at index: 4

Complexity Analysis

Time: O(log n) because we halve the search space each step using binary search logic

Space: O(1) because we use only a few variables, no extra space proportional to input

vs Alternative: Naive linear search is O(n) because it checks each element; this approach is much faster for large arrays

Edge Cases

empty array

returns -1 immediately since no elements to search

DSA C++

while (left <= right) {

array with one element equal to target

returns index 0 immediately

DSA C++

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

array with one element not equal to target

returns -1 after one check

DSA C++

while (left <= right) {

target not in array

returns -1 after search space is exhausted

DSA C++

return -1;

When to Use This Pattern

When you see a sorted array that has been rotated and need to find an element quickly, use this pattern of checking which half is sorted to guide binary search.

Common Mistakes

Mistake: Not checking which half is sorted before deciding where to search next
Fix: Always check if left half or right half is sorted to correctly narrow search

Mistake: Using mid = (left + right) / 2 without preventing overflow
Fix: Use mid = left + (right - left) / 2 to avoid integer overflow

Summary

Finds a target value in a rotated sorted array using modified binary search.

Use when you have a sorted array rotated at some pivot and need fast search.

The key is to identify which half is sorted to decide where to continue searching.