The O(n) Club: Find Minimum in Rotated Sorted Array II: The Binary Search Headache That Won’t Quit

The O(n) Club: Find Minimum in Rotated Sorted Array II – The Binary Search Headache That Won’t Quit

⚡ TL;DR

Got a sorted array, spun around its axis, and stuffed with duplicates? Congrats—you’re living the LeetCode 154 dream! Yes, you can always brute-force it like a 2003 script kiddie, but that’s O(n) and nobody’s impressed. The trick (well, the struggle): use a modified binary search. When duplicates block your path, baby steps! Example below:

// Brute force (because you hate yourself)
int min = nums[0];
for (int n : nums) min = Math.min(min, n);
 // Clever binary search (for actual humans)
public int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < nums[right]) right = mid;
        else if (nums[mid] > nums[right]) left = mid + 1;
        else right--;
    }
    return nums[left];
}

🧠 How Devs Usually Mess This Up

Most folks spot “rotated array” and instinctively apply regular binary search, high-fiving themselves until duplicates show up and ruin the party. When nums[mid] equals nums[right], you suddenly have no clue which side is which—classic “uh oh.” Old-school code will break, leaving you to stare at the screen like you just got Rickrolled by zeros.

🔍 What’s Actually Going On

Imagine a chef running through a carousel of identical cakes, desperately hunting for the one actual tiramisu. Your search window keeps shrinking, but when mid and right cakes look the same, you’re forced to check each one (‘right–’), grumbling as every duplicate stalls your delicious progress. Sometimes binary search is a Ferrari; with duplicates, it’s a rental scooter stuck in first gear.

🛠️ PseudoCode

• Start: left = 0, right = nums.length - 1 (embrace the uncertainty)
• While left < right:
  • Calculate mid = left + (right - left) / 2
  • If nums[mid] < nums[right]: Minimum lurks left, set right = mid
  • Else if nums[mid] > nums[right]: Minimum must be right, set left = mid + 1
  • Else (duplicates!): Bleh, just right-- and curse the universe
• Return nums[left]—the so-called minimum

💻 The Code

public int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < nums[right]) {
            right = mid;
        } else if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right--;
        }
    }
    return nums[left];
}

⚠️ Pitfalls, Traps & Runtime Smacks

• All duplicates? Tough luck. You’re slogging through O(n) whether you like it or not.
• Arrays like [2,2,2,0,1,2]: Don’t outsmart yourself—handle nums[mid] == nums[right] with care or your logic will melt.
• Complexity: Best case O(log n), worst case O(n) when you’re blessed by a thousand duplicates. Space is O(1)—so at least your RAM won’t cry.

🧠 Interviewer Brain-Tattoo

“If you have to do right-- in binary search, the universe is trolling you—but it’s also checking if you did your homework.” 🤷