Search in Rotated Sorted Array in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a rotated sorted array?

A rotated sorted array is an array that was originally sorted in ascending order but then rotated (shifted) at some pivot point. For example, [4,5,6,7,0,1,2] is a rotated version of [0,1,2,4,5,6,7].

beginner

Why can't we use simple binary search directly on a rotated sorted array?

Because the array is not fully sorted in ascending order due to rotation, simple binary search may fail. The array has two sorted parts separated by the pivot, so we need to identify which part to search in.

intermediate

In the rotated sorted array search algorithm, how do we decide which half to search next?

We check if the left half is sorted by comparing the start and middle elements. If sorted, we check if the target lies within this half. If yes, search left half; else, search right half. If left half is not sorted, the right half must be sorted, so we do the same check there.

beginner

What is the time complexity of searching in a rotated sorted array using the modified binary search?

The time complexity is O(log n) because each step halves the search space, similar to normal binary search.

beginner

Show the base case condition when the target is found in the rotated sorted array search.

If the middle element equals the target, return the middle index immediately. This stops the search.

What does a rotated sorted array look like?

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

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

C [4,5,6,7,0,1,2]

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

Option C is a sorted array rotated at a pivot. Others are fully sorted or unsorted.

Which method is best to search in a rotated sorted array?

A Simple binary search

B Modified binary search

C Linear search

D Bubble sort

Modified binary search handles the rotation by checking sorted halves.

If the left half of the array is sorted, and the target is within that range, where do we search next?

A Left half

B Both halves

C Right half

D None

We search the left half because the target lies there.

What is the worst-case time complexity of searching in a rotated sorted array using modified binary search?

A O(log n)

B O(n)

C O(n log n)

D O(1)

The search halves the array each time, so O(log n).

What should you check first in each step of the modified binary search?

A If target is at end

B If array is sorted

C If target is at start

D If middle element equals target

Always check if middle element is the target before other checks.

Explain how to search for a target in a rotated sorted array using binary search.

Think about how rotation splits the array into two sorted parts.

Describe why a simple binary search fails on a rotated sorted array and how the modified approach fixes it.

Focus on the effect of rotation on array order.

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