The O(n) Club: Rotated Array Minimum—Coffee-Powered Binary Search (Java Edition)
⚡ TL;DR
Looking for the smallest element in a rotated sorted array? Please don’t use a for-loop like you’re sorting beans by hand. Here’s the 10-second version, two ways:
// “Why am I doing this?” version: int min = nums[0]; for (int num : nums) min = Math.min(min, num); // But you WANT this (actual binary search): int findMin(int[] nums) { /* see below! */ }
🧠 How Devs Usually Mess This Up
Some devs see “sorted” and channel the ancient spirit of for (int i). Others spiral into anxiety over phantom duplicates, or argue with themselves about whether to compare the mid element to the left or right end of the array—and wind up comparing their life choices instead. Remember: no duplicates here (LeetCode 153 likes it simple). And always dance with the rightmost number during binary search, not the wall.
🔍 What’s Actually Going On
Picture a row of barista mugs: ordered by size, then rotated at some ungodly hour. Now the espresso cup is somewhere in the middle, but where? This “rotation point” is where the sorted order falls off a tiny caffeine cliff. The smallest mug (number) is right after this. Instead of taste-testing each mug (O(n)), use binary search: split the line, see which half is out of order, and chase the chaos until you’re down to one glorious, weary mug.
🛠️ PseudoCode
- Set
left = 0,right = nums.length - 1 - While
left < right: - Let
mid = left + (right - left) / 2 - If
nums[mid] > nums[right]: - The minimum is somewhere to the right of mid. So:
left = mid + 1 - Else:
- The minimum is at mid or to the left—shift:
right = mid - Loop ends when
left == right. You have found the chosen one:nums[left]
