DSA sheet · Binary Search · Classic pattern

Find Minimum in Rotated Sorted Array

A sorted array was rotated, and we must find its smallest value in O(log n). The teacher doesn't hand us a formula. She draws a few rotated arrays, puts left, mid and right on each, and discovers the rule by looking at where the minimum actually is. The rule she ends up with: compare nums[mid] with nums[right]. If the right half is sorted, the minimum is at mid or to its left. If not, it's strictly to the right.

Why it matters: it teaches the "mid might be the answer, so keep it" style of binary search (right = mid, while left < right). It also finds the rotation point, which is exactly what "Find K Rotations" asks for.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: scan for the smallest
• Part B · Optimal: binary search, compare mid with right
• Part C · Her homework: why not compare with left first?
• Part D · Revision page

Part 0 · Before starting

Why binary search works

Binary search checks the middle element and, from that single check, throws away half of the range for good. That's only safe if we can prove the answer is not in the half we drop. So the real work in every binary search problem is finding a yes/no test at mid that tells us which side the answer is on.

In this problem the test turns out to be "nums[mid] <= nums[right]?" Over a rotated array, its answers line up like no no no yes yes yes (no for the big piece, yes for the small piece), and the minimum is the first yes. That ordered yes/no pattern is exactly what binary search needs.

left, right, mid

• left = first index still in play (starts at 0); right = last index still in play (starts at n − 1).
• mid = left + (right - left) // 2: the middle index.

What is a rotated sorted array?

Rotating once (clockwise, to the right) moves the last element to the front. The teacher's example:

1 2 3 4   →   1 rotation:  4 1 2 3   →   2 rotations:  3 4 1 2

After rotating, the array is two sorted pieces: a piece of big values, then a piece of small values. The minimum is the first element of the second piece, right after the one place where the values drop. Rotating n times brings the array back to normal sorted order, and then there's no drop at all; the minimum is simply at index 0.

4 5 6 7 0 1 2      ← rotated 4 times: pieces "4 5 6 7" and "0 1 2", minimum 0
11 13 15 17        ← rotated 4 times with n = 4: fully sorted again, minimum 11

Part A · Brute force: scan for the smallest

LeetCode 153

1The question in simple words

You get nums, an array of unique values that was sorted in increasing order and then rotated between 1 and n times. Return the minimum value (the value, not its index).

• [3,4,5,1,2] → 1   [4,5,6,7,0,1,2] → 0   [11,13,15,17] → 11

2What the constraints tell us

• Length 1 to 5000 → never empty; 1 element is possible (then that element is the answer).
• Values −5000 to 5000, all unique → no ties, so comparisons between different cells are never equal.
• "You must write an algorithm that runs in O(log n) time." The teacher stresses this line: an O(n) loop would easily pass for n = 5000 (TLE starts around 10⁸ steps), but the problem itself demands binary search.

3Intuition

Look at every value and keep the smallest one seen so far.

4Why it's not enough

It ignores everything we know about the array (two sorted pieces). It's O(n), and the question explicitly asks for O(log n).

5Approach steps

1. Start with best = nums[0].
2. For every other value, if it's smaller, update best.
3. Return best.

6Code (Python)

class Solution:
    def findMin(self, nums):
        best = nums[0]
        for x in nums:
            if x < best:
                best = x
        return best

7Code line by line

8Dry run

[3,4,5,1,2]: best 3 → 3 → 3 → 1 → 1. Answer 1 after 5 looks.

9Complexity & remember

• Time O(n), space O(1). (Python's min(nums) does the same thing.)

Part B · Optimal: binary search, compare mid with right

1The question (same as Part A)

Return the minimum, but in O(log n).

2What the constraints tell us

• Unique values → when we compare nums[mid] with nums[right] and mid ≠ right, one is strictly bigger. So the test always gives a clear answer.
• At least 1 element → the loop below always ends with one index, and that index is valid.

3Intuition: look at where mid lands

The teacher's method: "I don't know any trick yet. I'll draw some cases, mark left, mid, right, and see what's true when the minimum is on each side." Here are her cases (drawn with my own numbers):

Case 1: right part NOT sorted → minimum is to the right of mid

index:   0   1   2   3   4
value:   3   4  [5]  1   2
         L      M       R
                └───────┘   mid..right = 5 1 2 → NOT sorted (drop 5→1)
nums[mid] = 5  >  nums[right] = 2

The drop is somewhere between mid and right, and the minimum sits just after the drop. So the minimum is to the right of mid. Mid itself (5) is in the "big" piece, so it can't be the minimum.

Case 2: right part sorted, and mid IS the minimum

index:   0   1   2   3   4
value:   4   5  [1]  2   3
         L      M       R
                └───────┘   mid..right = 1 2 3 → sorted ✓
nums[mid] = 1  <  nums[right] = 3      ← mid is the answer here

Case 3: right part sorted, mid is the minimum again

index:   0   1   2   3   4   5   6
value:   5   6   7  [1]  2   3   4
         L          M           R
                    └───────────┘   1 2 3 4 → sorted ✓, mid = 1 = minimum

Case 4: right part sorted, but mid is NOT the minimum

index:   0   1   2   3   4
value:   5   1  [2]  3   4
         L      M       R
                └───────┘   2 3 4 → sorted ✓, but the minimum (1) is on the LEFT

Put cases 2, 3 and 4 side by side. In all three, the right part is sorted. Sometimes mid is the answer (2, 3) and sometimes the answer is further left (4). But in none of them is the answer to the right of mid, because everything right of mid in a sorted part is bigger than nums[mid].

4Building the conditions

Rule 1: right part not sorted → left = mid + 1

The array is rotated clockwise, so the small values are pushed to the right. If mid..right is not sorted, the drop (and the minimum right after it) is in there. Everything from left to mid belongs to the big piece. We can throw all of it away, mid included: left = mid + 1.

Rule 2: right part sorted → right = mid (not mid - 1)

The minimum is at mid or to its left. Why mid and not mid - 1? The teacher's reason: mid - 1 means "I'm sure mid is not the answer". But cases 2 and 3 showed mid can be the answer. So we keep it: right = mid, and continue searching left..mid.

The loop: while left < right (not <=)

We keep shrinking until left and right meet. When they point to the same index, only one candidate is left, so that's the minimum. Return nums[left] (or nums[right]; they're the same cell).

5Approach steps

1. left = 0, right = n - 1.
2. While left < right: mid = left + (right - left) // 2.
3. If nums[mid] <= nums[right] (right part sorted) → right = mid.
4. Else (right part has the drop) → left = mid + 1.
5. Return nums[left].

6Code (Python)

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

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

            if nums[mid] <= nums[right]:   # right part sorted
                right = mid                # mid may be the minimum: keep it
            else:                          # right part has the drop
                left = mid + 1             # minimum is strictly right of mid

        return nums[left]                  # left == right: the only candidate

7Code line by line

8Dry run

Run 1: Case 1, [3,4,5,1,2] (the teacher's walk-through)

In step 2, mid lands on the same index as the new left. Since 1 < 2, we keep 1 and move right onto it. Now both pointers sit on the same cell, which is what stops the loop.

Run 2: Case 4, [5,1,2,3,4] (right part sorted, but the answer is to the left)

Run 3: [4,5,6,7,0,1,2] (LeetCode example 2)

mid 3 (7 > 2) → left = 4 · mid 5 (1 ≤ 2) → right = 5 · mid 4 (0 ≤ 1) → right = 4 · left == right → 0 ✓

Run 4: [11,13,15,17] (rotated n times = plain sorted)

mid 1 (13 ≤ 17) → right = 1 · mid 0 (11 ≤ 13) → right = 0 · return 11 ✓. With no drop, the "right part sorted" rule fires every time and walks right down to index 0.

9Complexity & remember

• Time O(log n): the teacher's reason: each step keeps one half and drops the other, so the range goes n → n/2 → n/4 → n/8 → … → 1. That's about log₂ n steps.
• Space O(1).

Part C · Her homework: why not compare with left first?

At the end of the video the teacher asks: "Why do we check whether the right half is sorted, and not the left half?" She says the logic fails if you check the left half first, and asks us to work out why on our own. Here is the answer.

1The question

Suppose we test nums[mid] >= nums[left] ("left half is sorted") instead. What should we do when it's true?

2What we can and can't conclude

3  4  [5]  1  2
L      M      R
└──────┘ sorted
min = 1 → right of mid

1  2  [3]  4  5
L      M      R
└──────┘ sorted
min = 1 → at left

3Intuition

In both A and B the same test is true (5 ≥ 3 and 3 ≥ 1). Yet in A we must go right, and in B we must stay left. One test, two different correct moves. That means the test alone can't decide which half to throw away. A fixed rule like "left half sorted → go right" gives the wrong answer on B (it would return 4).

Comparing with right doesn't have this problem. If nums[mid] < nums[right], nothing to the right of mid is smaller, so always go left (keep mid). If nums[mid] > nums[right], the drop is to the right, so always go right. Each test result has exactly one correct move.

4Can the left comparison be rescued?

Yes, with one extra check. The confusing case B is when the whole range left..right is already sorted. We can spot that first: if nums[left] < nums[right], there is no drop in the range, so the minimum is simply nums[left]. After that check, the range definitely contains the drop, and "left half sorted" really does mean "minimum is to the right".

5Approach steps (left-first, with the guard)

1. While left < right: if nums[left] < nums[right] → the range is sorted → return nums[left].
2. Otherwise compute mid. If nums[mid] >= nums[left] → mid is in the big piece → left = mid + 1.
3. Else mid is in the small piece and might be the minimum → right = mid.
4. Return nums[left].

6Code (Python)

class Solution:
    def findMin(self, nums):
        left, right = 0, len(nums) - 1
        while left < right:
            if nums[left] < nums[right]:   # no drop inside left..right
                return nums[left]
            mid = left + (right - left) // 2
            if nums[mid] >= nums[left]:    # mid is in the big piece
                left = mid + 1
            else:                          # mid is in the small piece
                right = mid
        return nums[left]

7Line by line (only the new parts)

8Dry run on case B, with and without the guard

9Complexity & remember

Still O(log n) time, O(1) space.

Part D · Revision page

s = Solution()
print(s.findMin([3, 4, 5, 1, 2]))           # 1
print(s.findMin([4, 5, 6, 7, 0, 1, 2]))     # 0
print(s.findMin([11, 13, 15, 17]))          # 11
print(s.findMin([5, 1, 2, 3, 4]))           # 1
print(s.findMin([7]))                       # 7

Based on this video: Find Minimum in Rotated Sorted Array