Why compare nums[mid] with nums[right] and not nums[left]?

nums[right] tells you which side the drop is on in every case. If nums[mid] > nums[right], the drop is between mid and right. Otherwise mid..right is ascending, so the minimum is at mid or before it. Comparing with nums[left] cannot tell an unrotated array from a rotated one.

Why is it right = mid and not right = mid - 1?

When nums[mid] <= nums[right], mid itself may be the minimum, so it has to stay in the range. Writing right = mid - 1 would skip it on inputs like [3, 1, 2].

What changes if the array has duplicates?

That is LeetCode 154. When nums[mid] == nums[right] the side of the drop cannot be decided, so the usual fix is right -= 1, which makes the worst case O(n).

Find Minimum in Rotated Sorted Array

Q: Why is it right = mid and not right = mid - 1?

When nums[mid] <= nums[right], mid itself may be the minimum, so it has to stay in the range. Writing right = mid - 1 would skip it on inputs like [3, 1, 2].

Q: What changes if the array has duplicates?

That is LeetCode 154. When nums[mid] == nums[right] the side of the drop cannot be decided, so the usual fix is right -= 1, which makes the worst case O(n).

Find the smallest element of a rotated sorted array of distinct values in O(log n) with binary search.

MediumSolve on LeetCode

Problem Understanding

Find Minimum in Rotated Sorted Array: an ascending array of distinct values was rotated between 1 and n times, so [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2]. Return the minimum element in O(log n) time.

Example: nums = [3, 4, 5, 1, 2] returns 1.

Attempt 1: Scan Every Element

Walk the array and keep the smallest value: O(n) time, O(1) space. It is correct, but it ignores what the problem gives you: the array is sorted except for one drop, and the minimum sits right after that drop. The problem asks for O(log n), which means halving the range at each step.

The Intuition: Find the Side of the Drop

A rotated sorted array is two ascending runs, and the minimum is the first element of the second run. Look at mid and right:

If nums[mid] > nums[right], the values fall somewhere between mid and right, so the drop, and the minimum, is to the right of mid: left = mid + 1.
Otherwise nums[mid..right] is ascending, so nothing to the right of mid is smaller than nums[mid]: the minimum is at mid or before it, right = mid.

Each step keeps the minimum inside [left, right] and halves the range. When left == right, that index is the minimum.

Interactive Walkthrough

L, M and R mark left, mid and right on every step, and everything outside the range is struck out. Watch how comparing nums[mid] with nums[right] always throws away the half that cannot hold the minimum.

Dry Run Table

Input: nums = [4, 5, 6, 7, 0, 1, 2]

`left`	`right`	`mid`	`nums[mid]` vs `nums[right]`	Move
0	6	3	7 > 2	`left = 4`
4	6	5	1 ≤ 2	`right = 5`
4	5	4	0 ≤ 1	`right = 4`
4	4	—	loop ends	return `nums[4] = 0`

The Solution Template

Binary search on the side of the drop, comparing mid with right.

Find Minimum in Rotated Sorted Array Code

1var findMin = function(nums) {
2    let left = 0, right = nums.length - 1;
3    while (left < right) {
4        const mid = Math.floor((left + right) / 2);
5        if (nums[mid] > nums[right]) {
6            left = mid + 1;
7        } else {
8            right = mid;
9        }
10    }
11    return nums[left];
12};

Edge Cases & Common Mistakes

Not rotated ([11, 13, 15, 17]): nums[mid] is never larger than nums[right], so right walks down to 0.
One element: the loop never runs and nums[0] is returned.
while (left <= right) with right = mid: when left == right the loop never ends. Use left < right.
right = mid - 1: skips mid when it is the minimum, as in [3, 1, 2].
Duplicates: this version assumes distinct values; see LeetCode 154 for the duplicate case.

Summary

Binary search does not need a target, only a test that tells you which half to keep. Here the test is nums[mid] > nums[right]: it points at the side of the drop, and the minimum is the first element after it. The same idea drives Search in Rotated Sorted Array.

More practice: DSA interview questions with answers · patterns cheat sheet

Search in Rotated Sorted Array

Search a 2D Matrix