The O(n) Club: Rotated Binary Search Mania (feat. Dizzy Arrays & Java)

The O(n) Club: Rotated Binary Search Mania (feat. Dizzy Arrays & Java)

⚡ TL;DR

Sorted array had a quarter-life crisis and rotated, but you still need to find your number before your coffee cools. Don’t brute force it (that’s O(n) regret). The slick way: one savvy binary search that finds the target—or admits defeat—fast.

// Java: Rotated binary search in a single pass
public int 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 mid;
        if (nums[left] <= nums[mid]) {
            // Left half sorted
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // Right half sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

🧠 How Devs Usually Mess This Up

Some devs think they need a two-phase plan: find the pivot (as if it’s shy), then binary search each half. Spoiler: you can skip the therapy session and do it all in one shot. Others forget that the array, post-rotation, isn’t monotonically increasing—it’s now a sorted parade with a conga-line twist in the middle, so plain binary search throws a tantrum and exits stage left. Don’t ignore the possibility that your target is right at mid, or you’ll end up debugging while consuming your weight in caffeine.

🔍 What’s Actually Going On

Imagine your sorted array like a sushi conveyor belt—except someone’s spun it around so the plates start at an unknown spot. Still, in every glance, at least half the belt is properly ordered (no wasabi next to desserts). Your job is to spot which half is behaving and see if your target is on that nice side or chilling in chaos. Every binary-search iteration is a little game: “Is left sorted? Then is the target there, or do we bail for right?” Ditch the pivot hunt, follow the order, win bragging rights.

🛠️ PseudoCode

• Start with pointers: left = 0, right = nums.length - 1.
• Loop while left <= right:
  • Set mid = left + (right - left) / 2 to avoid integer overflow (no, seriously).
  • If nums[mid] == target, congratulate yourself and return mid.
  • If nums[left] <= nums[mid] (left half is sorted):
    • If nums[left] <= target && target < nums[mid]: search left half (right = mid - 1).
    • Else: search right half (left = mid + 1).
  • Else (right half is sorted):
    • If nums[mid] < target && target <= nums[right]: search right half (left = mid + 1).
    • Else: search left half (right = mid - 1).
• If your pointers cross, just return -1 and blame the input, not your binary search.

💻 The Code

public int 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 mid;
        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 -1;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Searching for the pivot? Not needed. Don’t double your code or your blood pressure.
• Busted order assumptions: Post-rotation, only half is sorted at any time. Don’t trust everything you see.
• Classic fumbles: Forgetting to check nums[mid] == target right away, off-by-one pointer bugs at small array sizes, and thinking test case [1] is “too easy.”
• Complexity: Just O(log n) time and O(1) space—your RAM is bored, nothing blows up.

🧠 Interviewer Brain-Tattoo

“When life rotates your data, don’t pivot—just binary search smarter and act like you expected it all along.”