Search in Rotated Sorted Array in DSA C++ - Deep Dive

Overview - Search in Rotated Sorted Array

What is it?

A rotated sorted array is a sorted list that has been shifted around a pivot point. Searching in such an array means finding a target value efficiently despite this rotation. This problem requires adapting normal search methods to handle the shifted order. It is a common challenge in coding and algorithm interviews.

Why it matters

Without a special method, searching in a rotated sorted array would require checking each element one by one, which is slow for large lists. Efficient searching saves time and computing power, making programs faster and more responsive. This concept helps in real-world tasks like searching in circular buffers or rotated data logs.

Where it fits

Before this, you should understand basic binary search on sorted arrays. After mastering this, you can learn more complex search problems like searching in rotated arrays with duplicates or searching in 2D rotated matrices.

Mental Model

Core Idea

Even though the array is rotated, one half of it remains sorted, and we can use this property to decide where to search next.

Think of it like...

Imagine a clock face where the numbers are shifted but still in order around the circle. If you want to find a number, you check if it lies in the sorted half of the clock or the rotated half, then narrow down your search accordingly.

Array: [4,5,6,7,0,1,2]
Pivot here ->
Sorted half: [4,5,6,7]
Rotated half: [0,1,2]
Search target: 1
Check middle element, decide which half to search next based on sorted half property.

Build-Up - 6 Steps

1

Foundation

Understand Basic Binary Search

Concept: Binary search finds a target in a sorted array by repeatedly dividing the search interval in half.

Start with a sorted array like [1,2,3,4,5]. Pick the middle element. If it matches the target, stop. If the target is smaller, search the left half; if larger, search the right half. Repeat until found or no elements remain.

Result

Target found quickly or confirmed absent in O(log n) time.

Understanding binary search is essential because it forms the base for searching in rotated arrays efficiently.

2

Foundation

Recognize Rotated Sorted Array Structure

Concept: A rotated sorted array is a sorted array shifted around a pivot, splitting it into two sorted parts.

Example: Original sorted array [0,1,2,4,5,6,7] rotated at index 3 becomes [4,5,6,7,0,1,2]. Notice two sorted parts: [4,5,6,7] and [0,1,2].

Result

You can identify the pivot and the two sorted halves in the rotated array.

Knowing the array is split into two sorted halves helps us decide where to search next.

3

Intermediate

Modify Binary Search for Rotation

🤔Before reading on: do you think we can apply normal binary search directly on a rotated array? Commit to yes or no.

Concept: Adjust binary search to check which half is sorted and decide where the target might lie.

At each step, check if the left half is sorted by comparing start and middle elements. If sorted, check if target lies within this half. If yes, search left; else search right. If left half not sorted, right half must be sorted, apply same logic.

Result

Search narrows down correctly despite rotation, still in O(log n) time.

Understanding which half is sorted at each step allows us to maintain binary search efficiency even after rotation.

4

Intermediate

Handle Edge Cases in Search

🤔Before reading on: do you think the algorithm works if the array is not rotated at all? Commit to yes or no.

Concept: The method should also work if the array is fully sorted (no rotation) or rotated by its length (same as no rotation).

If the array is not rotated, the left half is always sorted, so the algorithm behaves like normal binary search. If rotated by array length, same applies. This confirms the method is robust.

Result

Algorithm works correctly for all rotation cases including no rotation.

Knowing the algorithm gracefully handles no rotation prevents unnecessary special cases.

5

Advanced

Implement Complete Search Algorithm in C++

🤔Before reading on: do you think the code will print the index of the target or -1 if not found? Commit to your answer.

Concept: Write a full C++ function that performs the search using the modified binary search logic.

int search(const vector& 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; if (nums[left] <= nums[mid]) { // Left half sorted if (nums[left] <= target && target < nums[mid]) right = mid - 1; else left = mid + 1; } else { // Right half sorted if (nums[mid] < target && target <= nums[right]) left = mid + 1; else right = mid - 1; } } return -1; } // Example usage: // vector arr = {4,5,6,7,0,1,2}; // int idx = search(arr, 0); // cout << idx << endl; // Output: 4

Result

The function returns the correct index of the target or -1 if not found.

Seeing the full code connects theory to practice and shows how to implement the logic efficiently.

6

Expert

Analyze Time Complexity and Limitations

🤔Before reading on: do you think the algorithm always runs in O(log n) time? Commit to yes or no.

Concept: Understand why the algorithm runs in logarithmic time and when it might degrade.

The algorithm halves the search space each step, so it runs in O(log n) time. However, if duplicates exist, the sorted half check can fail, causing worst-case O(n) time. Handling duplicates requires extra logic.

Result

Algorithm is efficient for unique elements but may slow down with duplicates.

Knowing the complexity limits helps choose the right algorithm for different data conditions.

Under the Hood

The algorithm uses a modified binary search that exploits the property that at least one half of the rotated array is sorted. By comparing boundary elements, it identifies the sorted half and decides where the target could be. This reduces the search space by half each iteration, maintaining logarithmic time.

Why designed this way?

Normal binary search fails because rotation breaks the global order. The design leverages local order in halves to restore binary search logic. Alternatives like linear search are slower. Handling duplicates complicates the design, so this approach balances efficiency and simplicity.

┌─────────────────────────────┐
│       Rotated Array         │
│ [4,5,6,7,0,1,2]            │
├─────────────┬───────────────┤
│ Left Half   │ Right Half    │
│ Sorted     │ Sorted        │
│ Check if target in left half │
│ If yes -> search left half    │
│ Else -> search right half     │
└─────────────────────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Can you apply normal binary search directly on a rotated sorted array? Commit to yes or no.

Common Belief: Normal binary search works fine on rotated sorted arrays without changes.

Reality: Normal binary search fails because the array is not fully sorted; rotation breaks the global order.

Why it matters: Using normal binary search leads to incorrect results or infinite loops.

Quick: Does the algorithm always run in O(log n) time even with duplicates? Commit to yes or no.

Common Belief: The search algorithm always runs in logarithmic time regardless of duplicates.

Reality: With duplicates, the sorted half check can fail, causing worst-case linear time.

Why it matters: Ignoring duplicates can cause performance degradation in real applications.

Quick: Is the pivot always at the middle of the array? Commit to yes or no.

Common Belief: The pivot (rotation point) is always at the middle index.

Reality: The pivot can be anywhere; the algorithm does not rely on pivot position but on sorted halves.

Why it matters: Assuming pivot at middle leads to wrong search logic and bugs.

Expert Zone

1

The algorithm's correctness depends on strict inequality checks to avoid infinite loops when elements are equal.

2

In presence of duplicates, a fallback linear scan may be needed to maintain correctness.

3

The approach can be extended to find the rotation pivot itself efficiently using similar logic.

When NOT to use

Avoid this algorithm if the array contains many duplicates; instead, use linear search or modified algorithms that handle duplicates explicitly.

Production Patterns

Used in systems with circular buffers, rotated logs, or time-series data where data is stored in rotated sorted order for efficiency.

Connections

Binary Search

Builds-on

Understanding binary search is crucial because the rotated array search adapts its core idea to handle rotation.

Circular Buffers

Application domain

Rotated sorted arrays model circular buffers where data wraps around; efficient search in such buffers uses similar logic.

Signal Processing

Pattern recognition

Detecting rotation points in arrays is analogous to identifying phase shifts in signals, showing cross-domain pattern detection.

Common Pitfalls

#1 Applying normal binary search without adjusting for rotation.

Wrong approach:

int search(const vector& 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;
if (target < nums[mid]) right = mid - 1;
else left = mid + 1;
}
return -1;
}

Correct approach:

int search(const vector& 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;
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;
}

Root cause:

Misunderstanding that rotation breaks the global sorted order, so normal binary search conditions fail.

#2 Ignoring duplicates causing infinite loops or wrong decisions.

Wrong approach:

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;
}

Correct approach:

while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
left++;
right--;
} else 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;
}
}

Root cause:

Not handling equal elements at boundaries causes ambiguity in deciding sorted half.

Key Takeaways

A rotated sorted array is a sorted array shifted around a pivot, splitting it into two sorted halves.

At least one half of the array is always sorted, which allows modified binary search to work.

Checking which half is sorted at each step guides the search direction efficiently.

The algorithm runs in O(log n) time for unique elements but may degrade with duplicates.

Understanding this problem deepens your grasp of binary search adaptations and real-world data structures.

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