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

Concept Flow - Find Minimum in Rotated Sorted Array

Start

↓

Set low=0, high=n-1

↓

Check if array[low

↓

Return array[low

↓

Find mid = (low+high)/2

↓

Compare array[mid

↓

mid

↓

Repeat loop

↓

Return array[low

↓

End

We use two pointers low and high to find the minimum by comparing middle and high elements, narrowing the search until low meets high.

Execution Sample

DSA C

int findMin(int* nums, int numsSize) {
  int low = 0, high = numsSize - 1;
  if (nums[low] < nums[high]) return nums[low];
  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 (nums)
1	Initialize pointers	0	6	-	-	low=0, high=6	[4,5,6,7,0,1,2]
2	Check if nums[low] < nums[high]	0	6	-	4 < 2? No	Proceed to loop	[4,5,6,7,0,1,2]
3	Calculate mid	0	6	3	-	-	[4,5,6,7,0,1,2]
4	Compare nums[mid] and nums[high]	0	6	3	7 > 2? Yes	low = mid + 1 = 4	[4,5,6,7,0,1,2]
5	Calculate mid	4	6	5	-	-	[4,5,6,7,0,1,2]
6	Compare nums[mid] and nums[high]	4	6	5	1 > 2? No	high = mid = 5	[4,5,6,7,0,1,2]
7	Calculate mid	4	5	4	-	-	[4,5,6,7,0,1,2]
8	Compare nums[mid] and nums[high]	4	5	4	0 > 1? No	high = mid = 4	[4,5,6,7,0,1,2]
9	Check loop condition	4	4	-	-	low == high, exit loop	[4,5,6,7,0,1,2]
10	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 4	After Step 6	After Step 8	Final
low	0	4	4	4	4
high	6	6	5	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 is sorted and where the minimum lies. See steps 4, 6, and 8 in execution_table where this comparison guides pointer changes.

Why does the loop stop when low equals high?

When low equals high, it means the search space is narrowed down to one element, which is the minimum. This is shown in step 9 where low=high=4.

What if the array is not rotated?

If the array is not rotated, nums[low] < nums[high] is true at step 2, so we return nums[low] immediately as the minimum.

Visual Quiz - 3 Questions

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

A 3

B 0

C 4

D 6

💡 Hint

Check the 'Pointer Changes' column at step 4 in execution_table.

At which step does the loop condition become false?

A Step 8

B Step 9

C Step 10

D Step 7

💡 Hint

Look for the step where low equals high and the loop exits in execution_table.

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

A high would move to mid each time

B high would move to mid + 1

C high would stay the same

D high would move to low

💡 Hint

Refer to pointer changes in steps 6 and 8 where nums[mid] <= nums[high].

Concept Snapshot

Find Minimum in Rotated Sorted Array:
- Use two pointers: low=0, high=n-1
- If nums[low] < nums[high], return nums[low]
- Else, binary search:
  - mid = (low+high)/2
  - If nums[mid] > nums[high], low = mid + 1
  - Else, high = mid
- Loop until low == high
- Return nums[low] as minimum

Full Transcript

This concept finds the minimum element in a rotated sorted array using a binary search approach. We start with two pointers, low and high, at the ends of the array. If the array is not rotated, the first element is the minimum. Otherwise, we repeatedly find the middle element and compare it with the element at high. If the middle element is greater, the minimum lies to the right, so we move low up. Otherwise, the minimum is at mid or to the left, so we move high down. We continue until low meets high, which points to the minimum element. 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 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