Find Minimum in Rotated Sorted Array in DSA Python

Mental Model

A rotated sorted array is like a sorted list that has been shifted. The smallest number is where the shift happened. We find it by checking the middle and deciding which half to search next.

Analogy: Imagine a clock face with numbers 1 to 12 in order. If you rotate the clock so 3 is at the top, the smallest number is where the clock 'starts' again after rotation. We look at the middle number to decide if the smallest is to the left or right.

Original sorted array:
[1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> null
Rotated array example:
[4] -> [5] -> [6] -> [7] -> [1] -> [2] -> [3] -> null
We want to find the smallest number (1) in the rotated array.

Dry Run Walkthrough

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

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

Step 1: Set left=0, right=6 (array ends), find mid=3

array: [4, 5, 6, 7, 1, 2, 3]
indices: 0  1  2  3  4  5  6
left=0, mid=3 (value=7), right=6 (value=3)

Why: We start by checking the middle to decide which half contains the minimum

Step 2: Since array[mid]=7 > array[right]=3, minimum is in right half, set left=mid+1=4

left=4, right=6
array segment: [1, 2, 3]
indices: 4  5  6

Why: If middle is greater than right, minimum must be to the right

Step 3: Calculate new mid=(4+6)//2=5, array[mid]=2

left=4, mid=5 (value=2), right=6 (value=3)

Why: Check middle of new segment to narrow down minimum location

Step 4: Since array[mid]=2 <= array[right]=3, minimum is in left half including mid, set right=mid=5

left=4, right=5
array segment: [1, 2]
indices: 4  5

Why: If middle is less or equal to right, minimum is at mid or left side

Step 5: Calculate new mid=(4+5)//2=4, array[mid]=1

left=4, mid=4 (value=1), right=5 (value=2)

Why: Check middle again to find minimum

Step 6: Since array[mid]=1 <= array[right]=2, set right=mid=4

left=4, right=4
array segment: [1]
index: 4

Why: Narrow down to single element which is minimum

Result:

Minimum value found at index 4: 1

Annotated Code

DSA Python

from typing import List

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]:
                left = mid + 1  # minimum must be in right half
            else:
                right = mid  # minimum is at mid or left half
        return nums[left]

# Driver code
if __name__ == '__main__':
    arr = [4, 5, 6, 7, 1, 2, 3]
    sol = Solution()
    print(sol.findMin(arr))

while left < right:

loop until search space reduces to one element

mid = (left + right) // 2

find middle index to check

if nums[mid] > nums[right]:

if middle element is greater than right, minimum is in right half

left = mid + 1 # minimum must be in right half

move left pointer to mid+1 to search right half

else:

otherwise minimum is at mid or left half

right = mid # minimum is at mid or left half

move right pointer to mid to include mid in search

return nums[left]

left now points to minimum element

Output

1

Complexity Analysis

Time: O(log n) because we halve the search space each step using binary search

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

vs Alternative: Naive approach scans all elements O(n), this binary search method is much faster for large arrays

Edge Cases

Array not rotated (fully sorted)

Minimum is the first element, algorithm returns it correctly

DSA Python

if nums[mid] > nums[right]:

Array rotated only once (minimum at last position)

Algorithm finds minimum by adjusting pointers correctly

DSA Python

left = mid + 1  # minimum must be in right half

Array with single element

Returns that element as minimum immediately

DSA Python

while left < right:

When to Use This Pattern

When you see a sorted array that might be rotated and need to find minimum or pivot quickly, use binary search to halve the search space based on middle and right values.

Common Mistakes

Mistake: Checking middle against left instead of right pointer
Fix: Compare nums[mid] with nums[right] to decide which half contains the minimum

Mistake: Using <= instead of < in while loop causing infinite loop
Fix: Use while left < right to ensure loop ends when pointers meet

Summary

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

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

The key is comparing middle element to right end 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 number where the rotation happened

B. To find the largest number in the array

C. To sort the array again

D. To count how many times the array was rotated

Solution

1. Step 1: Understand the rotated sorted array

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

2. Step 2: Identify the minimum element

   The minimum element is the smallest number, marking the rotation point.

3. Final Answer:

   To find the smallest number where the rotation happened -> Option A

4. Quick Check:

   Minimum = smallest number at rotation [OK]

Hint: Minimum is the smallest number where order breaks [OK]

Common Mistakes:

• Looking for the largest number instead
• Trying to sort the array again
• Counting rotations instead of finding minimum

2. Which of the following Python code snippets correctly initializes variables to find the minimum in a rotated sorted array nums using binary search?

easy

A. start, end = len(nums), 0

B. start = 1; end = len(nums)

C. start, end = 0, len(nums) - 1

D. start = -1; end = len(nums) + 1

Solution

1. Step 1: Understand binary search initialization

   Binary search uses start at 0 and end at last index (length - 1).

2. Step 2: Check each option

   start, end = 0, len(nums) - 1 correctly sets start=0 and end=len(nums)-1. Others have invalid ranges.

3. Final Answer:

   start, end = 0, len(nums) - 1 -> Option C

4. Quick Check:

   Binary search range = start=0, end=length-1 [OK]

Hint: Start at 0, end at last index for binary search [OK]

Common Mistakes:

• Setting start or end outside valid index range
• Using length instead of length - 1 for end
• Starting from 1 instead of 0

3. What will be the output of the following code snippet?

def find_min(nums):
    start, end = 0, len(nums) - 1
    while start < end:
        mid = (start + end) // 2
        if nums[mid] > nums[end]:
            start = mid + 1
        else:
            end = mid
    return nums[start]

print(find_min([3, 4, 5, 1, 2]))

medium

A. 2

B. 3

C. 5

D. 1

Solution

1. Step 1: Trace the binary search steps

   Initial array: [3,4,5,1,2], start=0, end=4 - mid=2, nums[mid]=5, nums[end]=2, 5>2 so start=mid+1=3 - now start=3, end=4 - mid=3, nums[mid]=1, nums[end]=2, 1<=2 so end=mid=3 - start=3, end=3, loop ends

2. Step 2: Return minimum element

   nums[start]=nums[3]=1 is the minimum.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   Minimum found = 1 [OK]

Hint: Compare mid and end to adjust search [OK]

Common Mistakes:

• Returning nums[mid] instead of nums[start]
• Not updating start or end correctly
• Confusing > and < in condition

4. The following code is intended to find the minimum in a rotated sorted array, but it has a bug. What is the bug?

def find_min(nums):
    start, end = 0, len(nums) - 1
    while start <= end:
        mid = (start + end) // 2
        if nums[mid] > nums[end]:
            start = mid + 1
        else:
            end = mid
    return nums[start]

medium

A. The loop condition should be start < end, not start <= end

B. The return statement should be nums[end], not nums[start]

C. The mid calculation is incorrect

D. The if condition should compare nums[mid] with nums[start]

Solution

1. Step 1: Analyze the loop condition

   The loop uses start <= end, which can cause infinite loop or index errors because start can pass end.

2. Step 2: Correct loop condition for binary search

   Using start < end ensures the loop stops when start meets end, correctly locating minimum.

3. Final Answer:

   The loop condition should be start < end, not start <= end -> Option A

4. Quick Check:

   Loop condition must be start < end [OK]

Hint: Use start < end for binary search loops [OK]

Common Mistakes:

• Using <= causes infinite loops or wrong indexes
• Changing mid calculation unnecessarily
• Comparing with wrong array element

5. Given a rotated sorted array that may contain duplicates, such as [2, 2, 2, 0, 1, 2], which modification to the binary search approach helps correctly find the minimum?

hard

A. Sort the array first before searching

B. When nums[mid] == nums[end], reduce end by 1 to skip duplicate

C. Always move start to mid + 1 when nums[mid] >= nums[end]

D. Return nums[0] directly as minimum

Solution

1. Step 1: Understand duplicates affect comparison

   When nums[mid] equals nums[end], we cannot decide which side minimum is on because duplicates hide order.

2. Step 2: Skip duplicate by reducing end

   Reducing end by 1 removes one duplicate and narrows search without missing minimum.

3. Final Answer:

   When nums[mid] == nums[end], reduce end by 1 to skip duplicate -> Option B

4. Quick Check:

   Handle duplicates by shrinking end [OK]

Hint: If mid equals end, reduce end by 1 to handle duplicates [OK]

Common Mistakes:

• Assuming no duplicates and using normal binary search
• Sorting array first wastes time
• Returning first element without checking