Here is solutions for Find Minimum in Rotated Sorted Array.

1. Understand the Problem

• You’re given a sorted array rotated at some pivot, and all elements are distinct. Return the minimum element.

[3, 4, 5, 1, 2] → 1
[1, 2, 3, 4] (not rotated) → 1
[2, 1] → 1

2. Clarify Constraints & Ask Questions

1. Are all elements unique?

• Yes.

1. Is array sorted in ascending order before rotation?

• Yes.

1. Is rotation exactly one segment shift?

• Yes, but may not rotate at all.

1. What is min array size?

• At least 1 element.

1. Negative numbers allowed?

• Yes.

1. Time constraints?

• Ideally O(log N) → use Binary Search.

3. Explore Examples

4. Brainstorm 2-3 solutions

4.1. Solution 1: Naive Solution - O(N)

• Traverse entire array → find min

• Time: O(n)

• Space: O(1).

4.2. Solution 2: Optimized (Binary Search — O(log n))

Key idea:

• If mid > right, minimum is right half

• If mid < right, minimum is left half (including mid)

5. Implement solutions

5.1. Brute Force - O(N)

class Solution:
    def findMin(self, nums: List[int]) -> int:
        return min(nums)

• Time: O(N).

• Space: O(1).

5.2. Binary Search (Handle duplicates) - O(logN)

Key idea:

• If mid >= right, minimum is right half

• If mid < right, minimum is left half (including mid)

=> But problems in the duplicate value: [1,1,1,1,0,1]

class Solution:
    def findMin(self, nums):
        left, right = 0, len(nums) - 1

        while left < right:
            mid = (left + right) // 2

            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]:
                right = mid
            else:  # nums[mid] == nums[right]
                right -= 1  # shrink search space

        return nums[left]

• Time: O(logN).

• Space: O(1).

6. Why we can not use the left to compare ?

• When a sorted array is rotated to the right, it splits into two sorted segments:

Original sorted:  [1, 2, 3, 4, 5]
Rotated:          [4, 5, | 1, 2, 3]
                   ↑      ↑
                 left   right

         First sorted     Second sorted (contains minimum)

=> So we can not use the left to compare.