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

Concept Flow - Find Minimum in Rotated Sorted Array

Start

↓

Check if array is rotated?

|Yes↓

Set low=0, high=n-1

↓

While low < high

↓

Find mid=(low+high)/2

↓

Compare nums[mid

↓

mid

↓

high = mid

↓

Repeat loop

↓

Return nums[low

↓

End

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 C#

int FindMin(int[] nums) {
  int low = 0, high = nums.Length - 1;
  while (low < high) {
    int mid = (low + high) / 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	Compare nums[mid] and nums[high]	Pointer Changes	Array State
1	Initialize pointers	0	6	-	-	low=0, high=6	[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	-	-	low == high, exit loop	[4,5,6,7,0,1,2]
6	Return minimum	4	4	-	-	Return nums[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 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 we move low. Otherwise, minimum is left side or at mid, so we move high. See steps 2 and 3 in execution_table.

Why does the loop stop when low equals high?

When low equals high, the search space is one element, which must be the minimum. The loop condition low < high ensures we stop exactly at the minimum index. See step 5 in execution_table.

What if the array is not rotated?

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

Visual Quiz - 3 Questions

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

A 3

B 0

C 4

D 6

💡 Hint

Check the 'Pointer Changes' column in step 2 where low is updated.

At which step does the loop condition become false?

A Step 5

B Step 3

C Step 4

D Step 6

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns in step 5 showing loop exit.

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

A high would increase

B high would decrease

C high would stay the same

D high would become equal to low immediately

💡 Hint

Refer to steps 3 and 4 where nums[mid] <= nums[high] causes high to move to mid.

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 minimum is the only point where order breaks

Full Transcript

This concept finds the smallest number in a rotated sorted array using binary search. We start with two pointers, low and high, at the ends of the array. We find the middle index and compare the middle element with the element at high. If the middle element is greater, the minimum must be 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 meets high, which points to the minimum. This method efficiently narrows down the search space in logarithmic time.

Practice

1. What is the main goal when finding the minimum in a rotated sorted array like [4, 5, 6, 7, 0, 1, 2]?

easy

A. To find the smallest element which is the rotation point

B. To find the largest element in the array

C. To sort the array again

D. To count how many times the array is rotated

Solution

1. Step 1: Understand the rotated sorted array

   A rotated sorted array is a sorted array shifted at some pivot. The smallest element is the rotation point.

2. Step 2: Identify the minimum element

   The minimum element is the smallest number where the rotation happened, which is the goal to find.

3. Final Answer:

   To find the smallest element which is the rotation point -> Option A

4. Quick Check:

   Minimum element = rotation point [OK]

Hint: Look for the smallest number where order breaks [OK]

Common Mistakes:

• Looking for the largest element instead
• Trying to sort the array again
• Counting rotations instead of finding minimum

2. Which of the following C# code snippets correctly initializes an array named nums with values [3, 4, 5, 1, 2]?

easy

A. int nums[] = new int[5] {3, 4, 5, 1, 2};

B. int nums = {3, 4, 5, 1, 2};

C. int[] nums = new int[4] {3, 4, 5, 1, 2};

D. int[] nums = new int[] {3, 4, 5, 1, 2};

Solution

1. Step 1: Check array declaration syntax in C#

   Correct syntax requires specifying type and using new int[] with initializer.

2. Step 2: Validate each option

   int[] nums = new int[] {3, 4, 5, 1, 2}; uses correct syntax. int nums = {3, 4, 5, 1, 2}; misses array type. int[] nums = new int[4] {3, 4, 5, 1, 2}; has size mismatch (4 vs 5 values). int nums[] = new int[5] {3, 4, 5, 1, 2}; mixes syntax incorrectly.

3. Final Answer:

   int[] nums = new int[] {3, 4, 5, 1, 2}; -> Option D

4. Quick Check:

   Correct array initialization syntax [OK]

Hint: Use 'new int[]' when initializing arrays with values [OK]

Common Mistakes:

• Omitting 'new int[]' keyword
• Declaring array without type
• Using wrong brackets or missing semicolon

3. What will be the output of the following C# code that finds the minimum in a rotated sorted array?

int[] nums = {4, 5, 6, 7, 0, 1, 2};
int left = 0, right = nums.Length - 1;
while (left < right) {
  int mid = left + (right - left) / 2;
  if (nums[mid] > nums[right]) {
    left = mid + 1;
  } else {
    right = mid;
  }
}
Console.WriteLine(nums[left]);

medium

A. 4

B. 7

C. 0

D. 2

Solution

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

   The code compares middle element with right to decide which half contains minimum.

2. Step 2: Trace the loop to find minimum index

   Loop narrows down to index of smallest element, which is 0 at index 4.

3. Final Answer:

   0 -> Option C

4. Quick Check:

   Minimum element found = 0 [OK]

Hint: Compare mid with right to find minimum side [OK]

Common Mistakes:

• Returning nums[mid] instead of nums[left]
• Confusing comparison direction
• Not updating pointers correctly

4. Identify the error in this C# code snippet intended to find the minimum in a rotated sorted array:

int[] nums = {3, 4, 5, 1, 2};
int left = 0, right = nums.Length - 1;
while (left <= right) {
  int mid = left + (right - left) / 2;
  if (nums[mid] > nums[right]) {
    left = mid + 1;
  } else {
    right = mid - 1;
  }
}
Console.WriteLine(nums[left]);

medium

A. The mid calculation is incorrect

B. The loop condition should be 'left < right' instead of 'left <= right'

C. The array initialization is wrong

D. The print statement should use 'right' instead of 'left'

Solution

1. Step 1: Analyze loop condition impact

   Using 'left <= right' can cause infinite loop or index out of range because pointers cross.

2. Step 2: Correct loop condition for binary search

   Changing to 'left < right' ensures loop stops when pointers meet at minimum.

3. Final Answer:

   The loop condition should be 'left < right' instead of 'left <= right' -> Option B

4. Quick Check:

   Proper loop condition avoids infinite loops [OK]

Hint: Use 'left < right' for binary search loops [OK]

Common Mistakes:

• Using <= causes pointer crossing errors
• Changing mid calculation unnecessarily
• Printing wrong index after loop

5. Given a rotated sorted array nums = [10, 12, 15, 1, 3, 6, 8], which code snippet correctly finds the minimum element using binary search?

hard

A. int left = 0, right = nums.Length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[right]) left = mid + 1; else right = mid; } Console.WriteLine(nums[left]);

B. int left = 0, right = nums.Length - 1; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] < nums[right]) right = mid - 1; else left = mid + 1; } Console.WriteLine(nums[left]);

C. int min = nums[0]; for (int i = 1; i < nums.Length; i++) { if (nums[i] < min) min = nums[i]; } Console.WriteLine(min); // Binary search used here

D. int left = 0, right = nums.Length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < nums[left]) right = mid; else left = mid + 1; } Console.WriteLine(nums[right]);

Solution

1. Step 1: Review binary search logic for minimum in rotated array

   The correct approach compares mid with right and adjusts pointers accordingly.

2. Step 2: Evaluate each option's correctness

   int left = 0, right = nums.Length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[right]) left = mid + 1; else right = mid; } Console.WriteLine(nums[left]); correctly implements binary search. int left = 0, right = nums.Length - 1; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] < nums[right]) right = mid - 1; else left = mid + 1; } Console.WriteLine(nums[left]); uses wrong loop condition and pointer updates. int min = nums[0]; for (int i = 1; i < nums.Length; i++) { if (nums[i] < min) min = nums[i]; } Console.WriteLine(min); // Binary search used here uses linear search, not binary. int left = 0, right = nums.Length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < nums[left]) right = mid; else left = mid + 1; } Console.WriteLine(nums[right]); compares mid with left incorrectly.

3. Final Answer:

   Option A code snippet -> Option A

4. Quick Check:

   Binary search with mid vs right comparison [OK]

Hint: Compare mid with right, move pointers to find minimum [OK]

Common Mistakes:

• Using linear search instead of binary
• Wrong loop conditions causing infinite loops
• Comparing mid with left instead of right