The O(n) Club: First and Last Index—Where Binary Search Gets Its Groove

The O(n) Club: First and Last Index—Where Binary Search Gets Its Groove

⚡ TL;DR

Problem: In a sorted array (possibly full of duplicates), find the first and last index of a target. If your target ghosted, return [-1, -1]. Brute force walks through the entire array like it’s on a sightseeing tour (O(n)). The VIP method uses binary search twice—once for each boundary:

// Please don't show this brute-force in interviews
int first = -1, last = -1;
for (int i = 0; i < nums.length; i++) {
    if (nums[i] == target) {
        if (first == -1) first = i;
        last = i;
    }
}
// O(n), but your interviewer wants to see that sweet log(n)

🧠 How Devs Usually Mess This Up

Most folks instinctively reach for the good ol’ for-loop—then wonder why interviewers look like they just bit into a lemon. The usual blunders:

🔍 What’s Actually Going On

Picture a shelf with perfectly sorted, eerily identical books (maybe Harry Potters). Your boss wants the positions of the first and last copy. Running back and forth between shelves? Overkill. Instead, use binary search: one sweep for the start, another for the end. That’s two O(log n) passes—the time savings will knock your boss’s socks off (and your CPU’s fans down).

• Left search: Find the first appearance—no cheating, keep nudging left even after you find the target.
• Right search: Same, but nudge right. Stop only when you absolutely cannot go further.

🛠️ PseudoCode

• Make a function: findBound(nums, target, isLeft). If isLeft, find the leftmost. If not, the rightmost.
• Initialize: int left = 0, right = nums.length - 1, result = -1;
• Binary search loop: While left <= right:

  int mid = left + (right - left) / 2;

  – If nums[mid] == target: set result = mid and – if isLeft: right = mid - 1 – else: left = mid + 1 – else if nums[mid] < target: left = mid + 1 – else: right = mid - 1
• Return result. Do it for both boundaries.
• Wrap it all up: return new int[] { leftIndex, rightIndex } (no sad zeros or empty arrays).

💻 The Code

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

⚠️ Pitfalls, Traps & Runtime Smacks

• Zero-length arrays: Don’t access what isn’t there, unless you crave that ArrayIndexOutOfBoundsException rush.
• Many duplicates? Don’t settle for the first hit—keep searching left or right as needed.
• Target absent: Both calls should cough up -1. (That’s what result = -1 is for.)
• Single-element arrays: If you find the target, both indices are zero. Don’t get fancy.
• Time complexity? Two passes of O(log n). Space? O(1). Your RAM gets a vacation for this one.

🧠 Interviewer Brain-Tattoo

“You’re not really doing binary search until you’re hunting for boundaries, not just value hits.” Stick that on your fridge—preferably with a magnetic debugger.