Find Minimum in Rotated Sorted Array in DSA C

Mental Model

A rotated sorted array is like a sorted list that has been shifted. The smallest element is the point where the shift happened.

Analogy: Imagine a clock face where the numbers are in order but the clock is rotated. The smallest number is where the clock starts again after the rotation.

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

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

Dry Run Walkthrough

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

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

Step 1: Set low=0, high=4 (start and end indices)

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

Why: We start searching the whole array

Step 2: Calculate mid = (0+4)/2 = 2, check element at mid=1

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

Why: Mid helps us decide which half contains the minimum

Step 3: Compare mid element (1) with high element (3), since 1 < 3, set high=mid=2

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

Why: Minimum must be in left half including mid

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

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

Why: Narrow down search to left half

Step 5: Compare mid element (5) with high element (1), since 5 > 1, set low=mid+1=2

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

Why: Minimum must be in right half excluding mid

Step 6: Now low=high=2, minimum found at index 2 with value 1

[4, 5, 1, 2, 3], low=2, high=2 -> minimum=1

Why: Search narrowed to one element which is minimum

Result:

Minimum element is 1 at index 2

Annotated Code

DSA C

#include <stdio.h>

int findMin(int* nums, int numsSize) {
    int low = 0;
    int high = numsSize - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] > nums[high]) {
            low = mid + 1;  // minimum is in right half
        } else {
            high = mid;     // minimum is in left half including mid
        }
    }
    return nums[low];
}

int main() {
    int nums[] = {4, 5, 1, 2, 3};
    int size = sizeof(nums) / sizeof(nums[0]);
    int min = findMin(nums, size);
    printf("Minimum element is %d\n", min);
    return 0;
}

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 greater than high, minimum is in right half

low = mid + 1; // minimum is in right half

move low pointer to mid+1 to discard left half

} else {

otherwise minimum is in left half including mid

high = mid; // minimum is in left half including mid

move high pointer to mid to narrow search

return nums[low];

return the minimum element found at low index

Output

Minimum element is 1

Complexity Analysis

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

Space: O(1) because only a few variables are used regardless of input size

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

Edge Cases

Array not rotated (e.g., [1, 2, 3, 4, 5])

Algorithm returns the first element as minimum correctly

DSA C

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

Array with single element (e.g., [10])

Returns the single element as minimum without entering loop

DSA C

while (low < high) {

Array rotated at last element (e.g., [2, 3, 4, 5, 1])

Algorithm correctly finds minimum at last index

DSA C

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

When to Use This Pattern

When you see a sorted array that might be rotated and need to find the smallest element quickly, use binary search to find the rotation point efficiently.

Common Mistakes

Mistake: Comparing nums[mid] with nums[low] instead of nums[high]
Fix: Compare nums[mid] with nums[high] to decide which half contains the minimum

Mistake: Using mid = (low + high) / 2 without preventing overflow
Fix: Use mid = low + (high - low) / 2 to avoid integer overflow

Mistake: Not updating low or high correctly causing infinite loop
Fix: Ensure low or high moves closer each iteration: low = mid + 1 or high = mid

Summary

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

Use when you have a sorted array shifted at some pivot and want to find the minimum efficiently.

The key insight is comparing middle and high elements to decide which half contains the minimum.

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 count how many times the array is rotated

D. To sort the array again

Solution

1. Step 1: Understand the rotated sorted array

   A rotated sorted array is originally sorted but then shifted. The smallest element is where the rotation happened.

2. Step 2: Identify the minimum element

   The minimum element is the smallest number and marks the rotation point in the array.

3. Final Answer:

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

4. Quick Check:

   Minimum element = rotation point [OK]

Hint: Minimum is the rotation point in the array [OK]

Common Mistakes:

• Looking for the largest element instead
• Trying to count rotations instead of finding minimum
• Sorting the array again unnecessarily

2. Which of the following C code snippets correctly initializes variables to find the minimum in a rotated sorted array nums of size n?

easy

A. int left = 0, right = n; int mid;

B. int left = 1, right = n; int mid;

C. int left = 0, right = n - 1; int mid;

D. int left = -1, right = n - 1; int mid;

Solution

1. Step 1: Set pointers to array bounds

   In C, array indices start at 0, so left should be 0 and right should be n-1.

2. Step 2: Declare mid variable

   Mid is used to find the middle index between left and right.

3. Final Answer:

   int left = 0, right = n - 1; int mid; -> Option C

4. Quick Check:

   Array indices start at 0, so left=0 and right=n-1 [OK]

Hint: Array indices start at 0, so right = n - 1 [OK]

Common Mistakes:

• Setting left or right outside valid index range
• Using right = n which is out of bounds
• Starting left at 1 instead of 0

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

int nums[] = {4, 5, 6, 7, 0, 1, 2};
int left = 0, right = 6, mid;
while (left < right) {
    mid = left + (right - left) / 2;
    if (nums[mid] > nums[right]) {
        left = mid + 1;
    } else {
        right = mid;
    }
}
printf("%d", nums[left]);

medium

A. 2

B. 0

C. 7

D. 4

Solution

1. Step 1: Understand the binary search logic

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

2. Step 2: Trace the loop to find minimum

   Loop narrows down to index 4 where value is 0, the smallest element.

3. Final Answer:

   0 -> Option B

4. Quick Check:

   Minimum element found = 0 [OK]

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

Common Mistakes:

• Printing nums[mid] instead of nums[left]
• Confusing greater than and less than in condition
• Not updating left or right correctly

4. Identify the error in the following C code that attempts to find the minimum in a rotated sorted array nums of size n:

int left = 0, right = n - 1, mid;
while (left <= right) {
    mid = left + (right - left) / 2;
    if (nums[mid] > nums[right]) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}
return nums[left];

medium

A. The mid calculation is incorrect

B. The if condition should compare nums[mid] < nums[right]

C. The return statement should be nums[right]

D. The loop condition should be left < right, not left <= right

Solution

1. Step 1: Analyze loop condition

   Using left <= right can cause infinite loop or out-of-bound access because left can surpass right.

2. Step 2: Correct loop condition

   Changing to left < right ensures the loop stops when left meets right, correctly locating minimum.

3. Final Answer:

   The loop condition should be left < right, not left <= right -> Option D

4. Quick Check:

   Loop condition left < right avoids infinite loops [OK]

Hint: Use left < right to avoid infinite loops [OK]

Common Mistakes:

• Using <= in loop condition causing infinite loops
• Incorrectly adjusting right pointer by mid - 1
• Returning nums[left] without proper loop exit

5. Given a rotated sorted array nums that may contain duplicates, which modification to the binary search approach helps correctly find the minimum element? A) Always move left pointer when nums[mid] == nums[right] B) Increase left pointer by one when nums[mid] == nums[right] C) Decrease right pointer by one when nums[mid] == nums[right] D) Return nums[mid] immediately when nums[mid] == nums[right]

hard

A. Decrease right pointer by one when nums[mid] == nums[right]

B. Increase left pointer by one when nums[mid] == nums[right]

C. Always move left pointer when nums[mid] == nums[right]

D. Return nums[mid] immediately when nums[mid] == nums[right]

Solution

1. Step 1: Understand duplicates in rotated array

   Duplicates can cause ambiguity when nums[mid] equals nums[right], so normal binary search fails.

2. Step 2: Adjust right pointer carefully

   When nums[mid] == nums[right], decreasing right by one helps skip duplicate safely without missing minimum.

3. Final Answer:

   Decrease right pointer by one when nums[mid] == nums[right] -> Option A

4. Quick Check:

   Handle duplicates by reducing right pointer [OK]

Hint: When equal, reduce right pointer to skip duplicates [OK]

Common Mistakes:

• Moving left pointer instead causing missed minimum
• Returning mid value prematurely
• Not handling duplicates causing wrong answer