# Find Minimum in Rotated Sorted Array

- **Canonical ID**: `find-minimum-in-rotated-sorted-array`
- **Canonical URL**: https://dsacheatsheet.com/problems/find-minimum-in-rotated-sorted-array
- **Difficulty**: medium
- **Patterns**: Binary Search
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

## 1. Core Invariant / The Trick

Compare `nums[mid]` strictly against `nums[r]` (the right boundary): if `nums[mid] > nums[r]`, the inflection point is strictly to the right (`l = mid + 1`); otherwise `mid` could be the minimum (`r = mid`).

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(log N)`
- **Space Complexity**: `O(1)`
- **Proof**: In any rotated array of distinct elements, comparing against `nums[r]` cleanly handles both unrotated (`nums[0] < nums[n-1]`) and rotated configurations.

## 3. Minimal Idiomatic Code

### Python
```python
def findMin(nums: list[int]) -> int:
    l, r = 0, len(nums) - 1
    while l < r:
        m = (l + r) // 2
        if nums[m] > nums[r]: l = m + 1
        else: r = m
    return nums[l]
```

### TypeScript
```typescript
export function findMin(nums: number[]): number {
  let l = 0, r = nums.length - 1;
  while (l < r) {
    const m = l + ((r - l) >> 1);
    if (nums[m] > nums[r]) l = m + 1; else r = m;
  }
  return nums[l];
}
```

### C++
```cpp
int findMin(vector<int>& n) {
    int l = 0, r = n.size() - 1;
    while (l < r) { int m = l + (r - l) / 2; n[m] > n[r] ? l = m + 1 : r = m; }
    return n[l];
}
```

### Java
```java
int findMin(int[] n) {
    int l = 0, r = n.length - 1;
    while (l < r) { int m = l + (r - l) / 2; if (n[m] > n[r]) l = m + 1; else r = m; }
    return n[l];
}
```

### Go
```go
func findMin(n []int) int {
    l, r := 0, len(n)-1
    for l < r {
        m := (l + r) / 2
        if n[m] > n[r] { l = m + 1 } else { r = m }
    }
    return n[l]
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Comparing against `nums[l]` fails cleanly when the remaining slice is unrotated!

### Follow-ups
- Array with duplicates: decrement `r--` when `nums[mid] == nums[r]`, worst case O(N).