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

Concept Flow - Find Minimum in Rotated Sorted Array

Start with full array

↓

Check if array is rotated?

↓

Use binary search

↓

Find mid element

↓

Compare mid with right

↓

Search right half

↓

Repeat until left == right

↓

Return element at left

Start by checking if array is rotated. If yes, use binary search comparing mid and right elements to narrow down the minimum until left meets right.

Execution Sample

DSA Javascript

function findMin(nums) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] > nums[right]) left = mid + 1;
    else right = mid;
  }
  return nums[left];
}

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

Execution Table

Step	Operation	Left Index	Right Index	Mid Index	Compare nums[mid] and nums[right]	Pointer Changes	Array State	Current Minimum Candidate
1	Initialize pointers	0	6	-	-	left=0, right=6	[4,5,6,7,0,1,2]	N/A
2	Calculate mid	0	6	3	nums[3]=7 > nums[6]=2	left = mid + 1 = 4	[4,5,6,7,0,1,2]	N/A
3	Calculate mid	4	6	5	nums[5]=1 <= nums[6]=2	right = mid = 5	[4,5,6,7,0,1,2]	N/A
4	Calculate mid	4	5	4	nums[4]=0 <= nums[5]=1	right = mid = 4	[4,5,6,7,0,1,2]	N/A
5	Check loop condition	4	4	-	-	left == right, loop ends	[4,5,6,7,0,1,2]	nums[4] = 0

💡 left equals right at index 4, minimum element found at nums[4] = 0

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
left	0	4	4	4	4
right	6	6	5	4	4
mid	-	3	5	4	4

Key Moments - 3 Insights

Why do we compare nums[mid] with nums[right] instead of nums[left]?

Comparing nums[mid] with nums[right] helps decide which half contains the minimum because the rightmost element is a reliable pivot in rotated arrays. See execution_table rows 2-4 where this comparison guides pointer moves.

Why does the loop stop when left equals right?

When left equals right, the search space is narrowed down to one element, which must be the minimum. This is shown in execution_table row 5 where left and right both are 4.

What if the array is not rotated?

If the array is not rotated, nums[mid] will always be less than or equal to nums[right], so right pointer moves left until left equals right, returning the first element. This is implied in the concept flow's 'No' branch.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'left' after step 2?

A 3

B 4

C 0

D 6

💡 Hint

Check the 'Pointer Changes' column in row 2 of execution_table.

At which step does the loop condition become false?

A Step 5

B Step 4

C Step 3

D Step 2

💡 Hint

Look at the 'Check loop condition' operation in execution_table row 5.

If nums[mid] was always less than nums[right], how would the pointers change?

A both pointers would stay the same

B left would move right

C right would move left

D left would move left

💡 Hint

Refer to pointer changes in execution_table rows 3 and 4 where nums[mid] <= nums[right].

Concept Snapshot

Find Minimum in Rotated Sorted Array
- Use binary search with left and right pointers
- Compare nums[mid] with nums[right]
- If nums[mid] > nums[right], move left to mid+1
- Else move right to mid
- Loop until left == right
- Return nums[left] as minimum

Full Transcript

This concept finds the minimum element in a rotated sorted array using binary search. We start with two pointers, left at 0 and right at the last index. We check if the array is rotated by comparing elements. Using binary search, we calculate mid and compare nums[mid] with nums[right]. If nums[mid] is greater, the minimum is in the right half, so we move left to mid+1. Otherwise, the minimum is in the left half, so we move right to mid. We repeat until left equals right, which points to the minimum element. This method efficiently narrows down the search space in logarithmic time.