Find Minimum in Rotated Sorted Array in DSA Go - Execution Trace

Concept Flow - Find Minimum in Rotated Sorted Array

Start

↓

Set low=0, high=len-1

↓

While low < high

↓

Calculate mid = (low+high)/2

↓

Compare nums[mid

↓

mid

↓

high = mid

↓

Repeat loop

↓

Return nums[low

We use two pointers low and high to narrow down the search space by comparing middle and high elements until low meets high, which points to the minimum.

Execution Sample

DSA Go

nums := []int{4,5,6,7,0,1,2}
low, high := 0, len(nums)-1
for low < high {
  mid := (low + high) / 2
  if nums[mid] > nums[high] {
    low = mid + 1
  } else {
    high = mid
  }
}
min := nums[low]

This code finds the minimum element in a rotated sorted array by binary searching with low and high pointers.

Execution Table

Step	Operation	low	high	mid	Compare nums[mid] and nums[high]	Pointer Changes	Array State
1	Initialize pointers	0	6	-	-	None	[4,5,6,7,0,1,2]
2	Calculate mid	0	6	3	nums[3]=7 > nums[6]=2	low = mid + 1 = 4	[4,5,6,7,0,1,2]
3	Calculate mid	4	6	5	nums[5]=1 <= nums[6]=2	high = mid = 5	[4,5,6,7,0,1,2]
4	Calculate mid	4	5	4	nums[4]=0 <= nums[5]=1	high = mid = 4	[4,5,6,7,0,1,2]
5	Check loop condition	4	4	-	-	Loop ends	[4,5,6,7,0,1,2]
6	Return minimum	4	4	-	-	Minimum found at index 4	[4,5,6,7,0,1,2]

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

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
low	0	4	4	4	4	4
high	6	6	5	4	4	4
mid	-	3	5	4	-	-

Key Moments - 3 Insights

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

Comparing nums[mid] with nums[high] helps decide which side contains the minimum. If nums[mid] > nums[high], minimum is right side, so low moves up (see Step 2). Otherwise, minimum is left side or at mid, so high moves down (see Steps 3 and 4).

Why does the loop stop when low equals high?

When low equals high, the search space is one element, which must be the minimum (see Step 5). Continuing would not narrow the search further.

What happens if the array is not rotated?

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

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the value of 'high' after the pointer change?

A 6

B 4

C 5

D 3

💡 Hint

Check the 'Pointer Changes' and 'high' column in Step 3 of execution_table.

At which step does the loop condition become false?

A Step 4

B Step 5

C Step 6

D Step 3

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns in Step 5 where loop ends.

If nums[mid] was always less than or equal to nums[high], how would 'low' change?

A low would stay the same

B low would increase each step

C low would decrease

D low would jump to high

💡 Hint

Refer to the 'Pointer Changes' column where low changes only if nums[mid] > nums[high].

Concept Snapshot

Find Minimum in Rotated Sorted Array:
- Use two pointers: low=0, high=len-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 by narrowing search space based on mid-high comparison

Full Transcript

This concept finds the minimum element in a rotated sorted array using a binary search approach. We start with two pointers, low at 0 and high at the last index. We calculate mid as the middle index between low and high. We compare the element at mid with the element at high. If nums[mid] is greater than nums[high], the minimum must be to the right of mid, so we move low to mid + 1. Otherwise, the minimum is at mid or to the left, so we move high to mid. We repeat this until low equals high, which points to the minimum element. This method efficiently finds the minimum in O(log n) time by narrowing the search space each step.