The O(n) Club: Search in Rotated Sorted Array II: Why Binary Search Needs Therapy

The O(n) Club: Search in Rotated Sorted Array II — Why Binary Search Needs Therapy

⚡ TL;DR

Rotated sorted array got you feeling dizzy? Now toss in duplicates, and yes, your clean binary search just got murky. Most of the time it’s quick—until duplicates force you to crawl through part of the data like a lost robot. Embrace the uncertainty!

// Brute force for drama-free correctness
for (int n : nums) {
    if (n == target) return true;
}
return false;

🧠 How Devs Usually Mess This Up

Dev sees “sorted array” and thinks classic O(log n) binary search, feeling slick. Sadly, when duplicates gather at the edges like a stand-up mob, all bets are off. Naive code copied from unique-number problems (looking at you, LeetCode 33) fails spectacularly as soon as test cases hurl 15,000 repeats of ‘2’ your way. Endpoints confused? Your “sorted half” logic is out to lunch.

🔍 What’s Actually Going On

Imagine searching for your friend’s number in a phonebook that some sleep-deprived AI rotated and filled with duplicate contacts. In normal binary search, you can always trust at least one side to be neatly arranged. But with duplicates all over? Suddenly, you can’t even tell where the book “starts.” If mid and right (or mid and left) are the same, you have to skip an endpoint and keep hoping. Sometimes it’s quick; sometimes you’re stuck shoveling through duplicates like a bored database indexer. Welcome to the glamorous O(n) worst case.

🛠️ PseudoCode

• Initialize two pointers: left = 0, right = nums.length - 1
• While left ≤ right:

  while (left <= right) {
      int mid = left + (right - left) / 2;
      ...
  }

• If nums[mid] == target: Easy win—go home early.
• If things are ambiguous (nums[mid] == nums[right]):
  • Panic slightly, then right-- (or left++) to dodge the ambiguity.
• Otherwise, check which side is sorted:
  • Left half sorted: nums[left] <= nums[mid]
    If nums[left] <= target && target < nums[mid], right = mid - 1; else left = mid + 1.
  • Right half sorted: Otherwise.
    If nums[mid] < target && target <= nums[right], left = mid + 1; else right = mid - 1.
• If loop ends, target’s a myth: Return false.

💻 The Code

public boolean search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return true;
        if (nums[mid] == nums[right]) {
            right--;
        } else if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return false;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• All elements same? Prepare for a linear search hangover.
• Zero-length array? Don’t panic; just return false.
• Ambiguous halves? Sometimes you’ll need to trim both ends before you see daylight.
• Time and space: Usually O(log n), but sometimes turns into a very slow parade. Space? Still O(1), at least something stays the same.

🧠 Interviewer Brain-Tattoo

“Duplicates at the gates? Don’t sweat it—just chip away and shrink the scope like every Friday deadline.”