Find Minimum in Rotated Sorted Array in DSA C#

Mental Model

A rotated sorted array is a sorted array shifted at some pivot. The smallest element is the only one where the order breaks. We find it by checking midpoints and narrowing the search.

Analogy: Imagine a clock face turned clockwise by some hours. The smallest number is where the clock starts again after 12. We look at the middle hour to decide which half to check next.

Original sorted array:
[1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> null

Rotated array example:
[4] -> [5] -> [6] -> [7] -> [1] -> [2] -> [3] -> null
               ↑                 ↑
             pivot             smallest

Dry Run Walkthrough

Input: array: [4, 5, 6, 7, 1, 2, 3]

Goal: Find the minimum element in the rotated sorted array efficiently

Step 1: Set low=0, high=6 (array bounds)

[4, 5, 6, 7, 1, 2, 3], low=0, high=6

Why: We start searching the whole array

Step 2: Calculate mid = (0+6)/2 = 3, check value at mid=7

[4, 5, 6, 7, 1, 2, 3], mid=3 (value=7)

Why: Midpoint helps decide which half contains the minimum

Step 3: Compare mid value 7 with high value 3; since 7 > 3, minimum is in right half, set low=mid+1=4

[4, 5, 6, 7, 1, 2, 3], low=4, high=6

Why: Right half must contain the smallest element

Step 4: Calculate mid = (4+6)/2 = 5, check value at mid=2

[4, 5, 6, 7, 1, 2, 3], mid=5 (value=2)

Why: Narrowing down to right half to find minimum

Step 5: Compare mid value 2 with high value 3; since 2 <= 3, minimum is in left half including mid, set high=mid=5

[4, 5, 6, 7, 1, 2, 3], low=4, high=5

Why: Minimum could be at mid or left side

Step 6: Calculate mid = (4+5)/2 = 4, check value at mid=1

[4, 5, 6, 7, 1, 2, 3], mid=4 (value=1)

Why: Check smaller segment for minimum

Step 7: Compare mid value 1 with high value 2; since 1 <= 2, set high=mid=4

[4, 5, 6, 7, 1, 2, 3], low=4, high=4

Why: Minimum found at index 4

Result:

[4, 5, 6, 7, 1, 2, 3], minimum element = 1 at index 4

Annotated Code

DSA C#

using System;

class RotatedSortedArray {
    public static int FindMin(int[] nums) {
        int low = 0;
        int high = nums.Length - 1;

        while (low < high) {
            int mid = low + (high - low) / 2;

            if (nums[mid] > nums[high]) {
                // Minimum must be in right half
                low = mid + 1;
            } else {
                // Minimum is at mid or in left half
                high = mid;
            }
        }
        return nums[low];
    }

    static void Main() {
        int[] arr = {4, 5, 6, 7, 1, 2, 3};
        int min = FindMin(arr);
        Console.WriteLine(min);
    }
}

while (low < high) {

loop until search space narrows to one element

int mid = low + (high - low) / 2;

calculate middle index to split search space

if (nums[mid] > nums[high]) {

if mid element is greater than high, minimum is in right half

low = mid + 1;

move low pointer to right half start

else { high = mid; }

otherwise minimum is at mid or left half, move high pointer

return nums[low];

low points to minimum element after loop ends

Output

1

Complexity Analysis

Time: O(log n) because the algorithm halves the search space each step

Space: O(1) because it uses only a few variables, no extra space proportional to input

vs Alternative: Compared to scanning all elements O(n), this binary search approach is much faster for large arrays

Edge Cases

Array not rotated (fully sorted)

Algorithm returns the first element as minimum

DSA C#

if (nums[mid] > nums[high]) { low = mid + 1; } else { high = mid; }

Array with single element

Returns that single element immediately

DSA C#

while (low < high) { ... } returns nums[low]

Array rotated at last element (minimum at end)

Algorithm correctly finds minimum at last index

DSA C#

if (nums[mid] > nums[high]) { low = mid + 1; } else { high = mid; }

When to Use This Pattern

When you see a sorted array that is rotated and need to find the smallest element quickly, use binary search by comparing middle and end elements to narrow down the minimum's location.

Common Mistakes

Mistake: Comparing mid element with low instead of high to decide search direction
Fix: Always compare nums[mid] with nums[high] to decide which half contains the minimum

Summary

Finds the smallest element in a rotated sorted array using binary search.

Use when you have a sorted array rotated at some pivot and need the minimum efficiently.

The key insight is comparing middle and high elements to decide which half to search next.

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