Find Minimum in Rotated Sorted Array in DSA C# - Time & Space Complexity

Time Complexity: Find Minimum in Rotated Sorted Array

O(log n)

Understanding Time Complexity

We want to know how fast we can find the smallest number in a rotated sorted array.

How does the time needed change as the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public 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];
}
    

This code finds the minimum value by using a binary search approach on a rotated sorted array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that halves the search range each time.
• How many times: The loop runs until the search space is reduced to one element, about log base 2 of n times.

How Execution Grows With Input

Each step cuts the array size roughly in half, so the number of steps grows slowly as the array grows.

Input Size (n)	Approx. Operations
10	About 4 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: Doubling the input size adds only one extra step.

Final Time Complexity

Time Complexity: O(log n)

This means the time to find the minimum grows slowly, even if the array gets much bigger.

Common Mistake

[X] Wrong: "Since the array is rotated, we must check every element to find the minimum, so it is O(n)."

[OK] Correct: The binary search approach uses the sorted property cleverly to skip half the elements each time, so it is much faster than checking all elements.

Interview Connect

Understanding this binary search pattern shows you can use smart searching methods, a key skill in many coding problems.

Self-Check

"What if the array was not rotated but still sorted? How would the time complexity change?"

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