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.