Find Minimum in Rotated Sorted Array in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a rotated sorted array?

A rotated sorted array is an array that was originally sorted in ascending order but then rotated (shifted) at some pivot point. For example, [4,5,6,7,0,1,2] is a rotated version of [0,1,2,4,5,6,7].

beginner

Why can't we just scan the entire rotated sorted array to find the minimum?

Scanning the entire array takes O(n) time, which is slower. Using the rotated sorted property, we can find the minimum in O(log n) time using a binary search approach.

intermediate

In the binary search for minimum in rotated sorted array, what does it mean if the middle element is greater than the rightmost element?

It means the minimum is in the right half of the array because the rotation point is to the right of mid.

beginner

What is the stopping condition for the binary search when finding the minimum in a rotated sorted array?

When the search space is reduced to one element, that element is the minimum.

intermediate

Show the C# code snippet to find the minimum in a rotated sorted array using binary search.

int FindMin(int[] nums) { 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; } } return nums[left]; }

What is the time complexity of finding the minimum in a rotated sorted array using binary search?

A O(n log n)

B O(log n)

C O(n)

D O(1)

Binary search divides the search space in half each time, resulting in O(log n) time.

If nums[mid] > nums[right], where is the minimum located?

A At right

B Left half including mid

C At mid

D Right half excluding mid

If middle element is greater than rightmost, minimum lies in the right half excluding mid.

What does it mean if nums[mid] <= nums[right] in the binary search?

A Minimum is in left half including mid

B Minimum is in right half excluding mid

C Array is not rotated

D Minimum is at right

If middle element is less or equal to rightmost, minimum is in left half including mid.

What is the initial search range for the binary search?

A From 0 to length-1

B From 1 to length

C From mid to right

D From left to mid

We start searching from the first to the last index of the array.

What is the minimum element in the array [3,4,5,1,2]?

A 5

B 2

C 1

D 3

1 is the smallest element after rotation.

Explain how binary search helps find the minimum in a rotated sorted array.

Think about how the middle element compares to the rightmost element.

Write the steps to find the minimum element in a rotated sorted array without scanning all elements.

Use binary search logic focusing on the rotation point.

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