Find Minimum in Rotated Sorted Array in DSA C++ - Execution Trace

Concept Flow - Find Minimum in Rotated Sorted Array

Start with full array

↓

Check if array is rotated?

Yes↓

Set low=0, high=n-1

↓

While low < high

↓

Find mid = (low+high)/2

↓

Compare mid element with high element

↓

Repeat loop

↓

Return element at low as minimum

We use two pointers low and high to narrow down the minimum element by comparing mid and high elements until low meets high.

Execution Sample

DSA C++

int findMin(vector<int>& nums) {
  int low = 0, high = nums.size() - 1;
  while (low < high) {
    int mid = low + (high - low) / 2;
    if (nums[mid] > nums[high]) low = mid + 1;
    else high = mid;
  }
  return nums[low];
}

This code finds the minimum element in a rotated sorted array using binary search.

Execution Table

Step	Operation	low	high	mid	nums[mid]	nums[high]	Pointer Changes	Visual State
1	Initialize pointers	0	6	-	-	-	low=0, high=6	[4,5,6,7,0,1,2]
2	Calculate mid	0	6	3	7	2	-	[4,5,6,7,0,1,2]
3	Compare nums[mid] > nums[high]	0	6	3	7	2	7 > 2 is True	[4,5,6,7,0,1,2]
4	Update low = mid + 1	4	6	-	-	-	low=4	[4,5,6,7,0,1,2]
5	Calculate mid	4	6	5	1	2	-	[4,5,6,7,0,1,2]
6	Compare nums[mid] > nums[high]	4	6	5	1	2	1 > 2 is False	[4,5,6,7,0,1,2]
7	Update high = mid	4	5	-	-	-	high=5	[4,5,6,7,0,1,2]
8	Calculate mid	4	5	4	0	1	-	[4,5,6,7,0,1,2]
9	Compare nums[mid] > nums[high]	4	5	4	0	1	0 > 1 is False	[4,5,6,7,0,1,2]
10	Update high = mid	4	4	-	-	-	high=4	[4,5,6,7,0,1,2]
11	Loop ends as low == high	4	4	-	-	-	-	[4,5,6,7,0,1,2]
12	Return nums[low]	4	4	-	0	-	-	[4,5,6,7,0,1,2]

💡 Loop ends when low equals high, pointing to the minimum element.

Variable Tracker

Variable	Start	After Step 4	After Step 7	After Step 10	Final
low	0	4	4	4	4
high	6	6	5	4	4
mid	-	3	5	4	4
nums[mid]	-	7	1	0	0
nums[high]	-	2	1	0	0

Key Moments - 3 Insights

Why do we compare nums[mid] with nums[high] instead of nums[low]?

Comparing nums[mid] with nums[high] helps us decide which half contains the minimum. If nums[mid] is greater than nums[high], the minimum is in the right half, so we move low up (see steps 3 and 4). Otherwise, it's in the left half or at mid, so we move high down (steps 6 and 7).

Why does the loop stop when low equals high?

When low equals high, it means we've narrowed down to one element, which must be the minimum (step 11). Continuing would not change the result.

What if the array is not rotated?

If the array is not rotated, nums[mid] will always be less than or equal to nums[high], so high moves down until low equals 0, returning the first element as minimum.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of low after step 4?

A 3

B 0

C 4

D 6

💡 Hint

Check the 'Pointer Changes' and 'low' column in row for step 4.

At which step does the loop end because low equals high?

A Step 11

B Step 12

C Step 10

D Step 9

💡 Hint

Look for the row where 'Loop ends as low == high' in the 'Operation' column.

If nums[mid] was always less than nums[high], which pointer would move?

A low pointer moves up

B high pointer moves down

C both pointers move

D no pointer moves

💡 Hint

Refer to steps 6 and 9 where nums[mid] <= nums[high] and high is updated.

Concept Snapshot

Find Minimum in Rotated Sorted Array:
- Use binary search with low=0, high=n-1
- While low < high:
  - mid = (low+high)/2
  - If nums[mid] > nums[high], low = mid+1
  - Else high = mid
- Return nums[low] as minimum
- Works because rotation splits sorted array into two sorted parts

Full Transcript

This concept shows how to find the minimum element in a rotated sorted array using binary search. We start with two pointers, low at 0 and high at the last index. We calculate mid and compare nums[mid] with nums[high]. If nums[mid] is greater, the minimum lies to the right, so we move low up. Otherwise, the minimum is at mid or to the left, so we move high down. We repeat until low equals high, which points to the minimum element. This method efficiently narrows down the search space by half each time.

Practice

1. What is the main idea behind finding the minimum element in a rotated sorted array?

easy

A. Use a hash map to store elements and find the minimum

B. Sort the array again and pick the first element

C. Traverse the array linearly and pick the smallest element

D. Use binary search to find the point where the order breaks

Solution

1. Step 1: Understand the rotated sorted array property

   A rotated sorted array is sorted but rotated at some pivot point, causing a break in order.

2. Step 2: Use binary search to find the break point

   Binary search helps find the pivot where the order breaks, which is the minimum element.

3. Final Answer:

   Use binary search to find the point where the order breaks -> Option D

4. Quick Check:

   Binary search finds minimum in rotated array [OK]

Hint: Look for the pivot where order breaks using binary search [OK]

Common Mistakes:

• Trying to sort the array again wastes time
• Linear search is slower than binary search
• Using extra space unnecessarily

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

easy

A. while (left <= right) { int mid = left + (right - left) / 2; }

B. while (left < right) { int mid = (left + right) / 2; }

C. for (int left = 0, right = nums.size() - 1; left <= right; )

D. for (int i = 0; i < nums.size(); i++)

Solution

1. Step 1: Understand binary search loop conditions

   For finding minimum in a rotated sorted array, the binary search loop typically uses while (left < right) to avoid infinite loops and correctly narrow down the search space.

2. Step 2: Check correct mid calculation and loop condition

   while (left < right) { int mid = (left + right) / 2; } is the common and correct approach for this problem.

3. Final Answer:

   while (left < right) { int mid = (left + right) / 2; } -> Option B

4. Quick Check:

   Correct binary search loop syntax for this problem [OK]

Hint: Use while with left < right and mid calculation [OK]

Common Mistakes:

• Using for loop instead of while for binary search
• Calculating mid as left + (right - left) / 2 with wrong loop condition
• Using wrong loop condition like left <= right causing infinite loop

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

std::vector<int> nums = {4,5,6,7,0,1,2};
int left = 0, right = nums.size() - 1;
while (left < right) {
  int mid = left + (right - left) / 2;
  if (nums[mid] > nums[right]) left = mid + 1;
  else right = mid;
}
std::cout << nums[left] << std::endl;

medium

A. 0

B. 4

C. 7

D. 2

Solution

1. Step 1: Understand the binary search logic on rotated array

   The code compares nums[mid] with nums[right] to decide which half to keep.

2. Step 2: Trace the loop to find minimum

   Since nums[mid] > nums[right], left moves to mid+1 until left == right at index of minimum (0).

3. Final Answer:

   0 -> Option A

4. Quick Check:

   Minimum element found is 0 [OK]

Hint: Compare mid and right to narrow search for minimum [OK]

Common Mistakes:

• Confusing mid and right comparison direction
• Printing nums[right] instead of nums[left]
• Not updating left or right correctly

4. Identify the error in the following code snippet that tries to find the minimum in a rotated sorted array:

int findMin(std::vector<int>& nums) {
  int left = 0, right = nums.size() - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] > nums[right]) left = mid + 1;
    else right = mid - 1;
  }
  return nums[left];
}

medium

A. The else block should set right = mid, not right = mid - 1

B. The loop condition should be left < right, not left <= right

C. The mid calculation causes overflow

D. The return statement should return nums[right], not nums[left]

Solution

1. Step 1: Analyze the binary search update rules

   When nums[mid] <= nums[right], the minimum is at mid or left side, so right should be set to mid.

2. Step 2: Identify incorrect update causing skipping minimum

   Setting right = mid - 1 skips mid, possibly missing the minimum element.

3. Final Answer:

   The else block should set right = mid, not right = mid - 1 -> Option A

4. Quick Check:

   Correct right update avoids missing minimum [OK]

Hint: Set right = mid to include mid in search [OK]

Common Mistakes:

• Using left <= right causes infinite loop
• Returning nums[left] is correct
• Mid calculation is safe here

5. Given a rotated sorted array nums that may contain duplicates, which modification is needed in the binary search approach to correctly find the minimum element?

hard

A. If nums[mid] == nums[right], return nums[mid] immediately

B. If nums[mid] == nums[right], increase left by one to skip duplicate

C. If nums[mid] == nums[right], reduce right by one to skip duplicate

D. Duplicates do not affect the binary search logic

Solution

1. Step 1: Understand impact of duplicates on binary search

   Duplicates can cause ambiguity when nums[mid] == nums[right], making it unclear which side to choose.

2. Step 2: Modify search by reducing right to skip duplicate

   Reducing right by one helps shrink the search space safely without missing the minimum.

3. Final Answer:

   If nums[mid] == nums[right], reduce right by one to skip duplicate -> Option C

4. Quick Check:

   Handle duplicates by shrinking right pointer [OK]

Hint: When equal, reduce right to skip duplicates safely [OK]

Common Mistakes:

• Returning immediately on equality misses minimum
• Increasing left instead of reducing right causes errors
• Ignoring duplicates leads to wrong answers