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.

Practice

1. What is the main challenge when searching for an element in a rotated sorted array compared to a normal sorted array?

easy

A. The array is not fully sorted, so normal binary search cannot be directly applied.

B. The array contains duplicate elements which confuse the search.

C. The array size is unknown, so we cannot set search boundaries.

D. The array elements are all negative numbers.

Solution

1. Step 1: Understand normal binary search assumption

   Binary search works efficiently on fully sorted arrays by comparing mid element to target.

2. Step 2: Identify the problem with rotated arrays

   Rotated sorted arrays are sorted but shifted, so the order is broken at the rotation point, making direct binary search invalid.

3. Final Answer:

   The array is not fully sorted, so normal binary search cannot be directly applied. -> Option A

4. Quick Check:

   Rotated array breaks sorted order = need modified search [OK]

Hint: Look for the rotation point to adjust binary search [OK]

Common Mistakes:

• Assuming array is fully sorted and applying normal binary search
• Ignoring rotation and searching linearly
• Confusing duplicates with rotation

2. Which of the following is the correct syntax to start a binary search loop for a rotated sorted array in C++?

easy

A. if (arr[mid] == target)

B. for (int i = 0; i < n; i++)

C. while (start <= end)

D. do { ... } while (start < end)

Solution

1. Step 1: Identify loop type for binary search

   Binary search uses a while loop with condition start <= end to narrow search range.

2. Step 2: Check options for correct loop syntax

   while (start <= end) uses while (start <= end), which is standard for binary search loops.

3. Final Answer:

   while (start <= end) -> Option C

4. Quick Check:

   Binary search loop uses while (start <= end) [OK]

Hint: Binary search loops use while (start <= end) [OK]

Common Mistakes:

• Using for loop instead of while for binary search
• Using incorrect loop condition like start < end
• Confusing if statement with loop

3. What will be the output of the following C++ code snippet?

int arr[] = {4,5,6,7,0,1,2};
int target = 0;
int start = 0, end = 6;
int result = -1;
while (start <= end) {
  int mid = start + (end - start) / 2;
  if (arr[mid] == target) {
    result = mid;
    break;
  }
  if (arr[start] <= arr[mid]) {
    if (target >= arr[start] && target < arr[mid])
      end = mid - 1;
    else
      start = mid + 1;
  } else {
    if (target > arr[mid] && target <= arr[end])
      start = mid + 1;
    else
      end = mid - 1;
  }
}
std::cout << result << std::endl;

medium

A. 3

B. 0

C. -1

D. 4

Solution

1. Step 1: Trace initial variables and mid calculation

   start=0, end=6, mid=3 (element 7). arr[mid] != target (0).

2. Step 2: Check which half is sorted and adjust search

   arr[start]=4 <= arr[mid]=7, left half sorted. Target 0 not in [4,7), so search right half: start=mid+1=4.

3. Step 3: Next iteration mid=5 (element 1)

   arr[mid]=1 != target. arr[start]=0 <= arr[mid]=1, left half sorted. Target 0 in [0,1), so end=mid-1=4.

4. Step 4: Next iteration mid=4 (element 0)

   arr[mid]=0 == target, result=4, break loop.

5. Final Answer:

   4 -> Option D

6. Quick Check:

   Target 0 found at index 4 [OK]

Hint: Check sorted half and adjust start/end accordingly [OK]

Common Mistakes:

• Not updating start/end correctly based on sorted half
• Confusing indices and returning wrong index
• Missing break after finding target

4. Identify the bug in the following code snippet for searching in a rotated sorted array:

int search(int arr[], int n, int target) {
  int start = 0, end = n - 1;
  while (start < end) {
    int mid = start + (end - start) / 2;
    if (arr[mid] == target) return mid;
    if (arr[start] <= arr[mid]) {
      if (target >= arr[start] && target < arr[mid])
        end = mid - 1;
      else
        start = mid + 1;
    } else {
      if (target > arr[mid] && target <= arr[end])
        start = mid + 1;
      else
        end = mid - 1;
    }
  }
  return -1;
}

medium

A. The mid calculation is incorrect and can cause overflow.

B. The loop condition should be while (start <= end) instead of while (start < end).

C. The target comparison should use > instead of >=.

D. The function does not handle empty arrays.

Solution

1. Step 1: Analyze loop condition impact

   Using while (start < end) misses checking when start == end, possibly skipping last element.

2. Step 2: Correct loop condition for complete search

   Changing to while (start <= end) ensures all elements are checked, including when start equals end.

3. Final Answer:

   The loop condition should be while (start <= end) instead of while (start < end). -> Option B

4. Quick Check:

   Loop must cover start == end to check last element [OK]

Hint: Use while (start <= end) for full binary search coverage [OK]

Common Mistakes:

• Using while (start < end) and missing last element
• Ignoring overflow in mid calculation (not in this code though)
• Incorrect comparison operators

5. Given a rotated sorted array arr = {15, 18, 2, 3, 6, 12}, write a C++ function to find the index of the minimum element. What is the output of your function?

hard

A. 2

B. 0

C. 5

D. 3

Solution

1. Step 1: Understand the minimum element in rotated array

   The minimum element is the rotation point where order breaks. Here, 2 at index 2 is smallest.

2. Step 2: Use binary search to find minimum

   Check mid and compare with end to decide which half contains minimum. Eventually, index 2 is found.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Minimum element 2 is at index 2 [OK]

Hint: Compare mid element with end to find rotation point [OK]

Common Mistakes:

• Returning first element index instead of minimum
• Confusing maximum with minimum element
• Not handling rotation correctly