Find First and Last Position in Sorted Array: Binary Search Done Right

Most candidates overthink this problem and fall into classic binary search traps. Here's the clean lower_bound/upper_bound approach that interviewers love.

The Problem (And Why It Trips People Up)#

Here's the prompt you'll see on LeetCode — and increasingly in real interviews at companies like Google, Meta, and Amazon:

Given a sorted array of integers, find the starting and ending position of a given target value. If the target is not found in the array, return [-1, -1]. Your solution must run in O(log n) time.

Sounds simple, right? Find where the target starts, find where it ends. But here's the thing most people miss — the moment you try to write two separate "find first" and "find last" binary searches from scratch, you're inviting bugs. The <= vs < confusion alone is responsible for so many failed interviews.

I've watched hundreds of candidates spiral on this one. They start confident, hit an off-by-one error, try to patch it, make it worse, and then freeze. Today, we're going to make sure that's not you.

What the Interviewer Is Really Testing#

When a senior engineer asks you this question, they're not just checking if you know binary search exists. They're looking for a few very specific signals:

• Do you recognize the boundary search pattern? Strong candidates don't reinvent the wheel — they reach for lower_bound and upper_bound abstractions.
• Can you handle edge cases proactively? Empty arrays, targets not in the array, all elements being the same — do you think about these before coding or after?
• Is your code clean and reusable? Writing two helper functions instead of one messy monolith signals strong engineering instincts.
• Do you communicate your thought process? An interviewer would rather see a confident, slightly imperfect solution explained well than a perfect solution delivered in silence.

A weak answer looks like: jumping straight to code, writing ad-hoc binary search logic, and getting tangled in the termination condition. A strong answer looks like: pausing, reframing the problem in terms of boundaries, and writing clean, symmetric helper functions.

The Mental Model Shift That Changes Everything#

Stop thinking about this as:

"Find first occurrence" + "Find last occurrence"

Start thinking about it as:

Find the left boundary + Find the right boundary

More precisely:

• Lower Bound → the first index where nums[i] >= target
• Upper Bound → the first index where nums[i] > target

Once you have those two, your answer is just:

start = lowerBound(target)
end   = upperBound(target) - 1

This reframe is cleaner, less error-prone, and — here's the interviewer bonus — it maps directly to std::lower_bound and std::upper_bound in C++, which shows you understand standard library design. Mentioning that connection will genuinely impress most interviewers.

The Two Patterns You Must Memorize#

Forget trying to derive these on the fly under pressure. Burn these into your brain now.

Lower Bound — First index where nums[i] >= target#

public int lowerBound(int[] nums, int target) {
    int l = 0, r = nums.length; // note: r = length, not length - 1
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] < target) {
            l = mid + 1; // target is to the right
        } else {
            r = mid;     // mid could be the answer, keep it in range
        }
    }
    return l;
}

Upper Bound — First index where nums[i] > target#

public int upperBound(int[] nums, int target) {
    int l = 0, r = nums.length;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] <= target) {
            l = mid + 1; // target is at mid or to the right
        } else {
            r = mid;
        }
    }
    return l;
}

Spot the difference? It's one character: < vs <= in the condition. That single character is what separates lower bound from upper bound. Tiny change, completely different behavior. This is exactly why candidates mess it up under pressure — so let's anchor it with a memory trick:

• Lower bound: stop when you find something >= target → condition moves left only when target → condition moves left only when <= target

The Complete Solution#

Let's put it all together:

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int start = lowerBound(nums, target);
        int end = upperBound(nums, target) - 1;
 
        // Critical check: target might not exist in the array
        if (start >= nums.length || nums[start] != target) {
            return new int[]{-1, -1};
        }
 
        return new int[]{start, end};
    }
 
    public int lowerBound(int[] 

Time Complexity: O(log n) — two binary searches, each O(log n) Space Complexity: O(1) — no extra data structures

Walking Through an Example#

Let's trace through this together so it's crystal clear before your interview.

nums = [1, 2, 2, 2, 3]
target = 2

lowerBound(nums, 2):

• l=0, r=5 → mid=2, nums[2]=2, not < 2 → r=2
• l=0, r=2 → mid=1, nums[1]=2, not < 2 → r=1
• l=0, r=1 → mid=0, nums[0]=1, 1 < 2 → l=1
• l=1, r=1 → loop exits → return 1 ✅

upperBound(nums, 2):

• l=0, r=5 → mid=2, nums[2]=2, 2 2 → r=4
• l=3, r=4 → mid=3, nums[3]=2, 2 <= 2 → l=4
• l=4, r=4 → loop exits → return 4 ✅

Result: start=1, end=4-1=3 → [1, 3] ✓

Where Candidates Get Stuck#

I've seen the same mistakes so many times I can predict them. Here's your cheat sheet of what to watch out for:

• Mixing up < and <= — This is the #1 killer. One wrong operator flips lower bound into upper bound logic, and your answer is silently wrong. Always re-read your condition before moving on.
• Forgetting to subtract 1 from upper bound — Upper bound returns the first index greater than target. The last occurrence is one step before that. Don't return upperBound directly.
• Not checking if the target exists — After computing start, you must verify nums[start] == target. Binary search will always return some index — it won't tell you the target isn't there.
• Using r = nums.length - 1 inconsistently — If you initialize r = nums.length (half-open interval), your loop condition must be l < r. If you use r = nums.length - 1 (closed interval), the logic changes entirely. Mixing these kills you.
• Swapping the logic between the two functions — Writing lower bound logic but naming it findLast, or vice versa. Always map your condition to its semantic meaning before you write a single line.

How to Talk Through This in an Interview#

This is where most people leave points on the table. The code is only half the battle — your narration matters. Here's exactly how I'd recommend framing it:

When you first read the problem:

"My first instinct is to use binary search since the array is sorted and we need O(log n). But instead of writing two separate searches for first and last occurrence — which gets messy with boundary conditions — I'd rather think about this as finding a lower bound and an upper bound."

When you start coding:

"I'll write two helper functions. Lower bound gives me the first index where the value is greater than or equal to the target. Upper bound gives me the first index where the value is strictly greater than the target. The key difference is just whether I use < or <= in the condition."

When handling the edge case:

"Before I return, I need to check whether the target actually exists in the array. Lower bound will always return some index — it could be pointing to a completely different number if the target isn't present. So I'll verify nums[start] == target."

When you finish:

"This runs in O(log n) time with O(1) space — two binary searches but they're both logarithmic. Want me to walk through a test case or talk about any edge cases?"

That last line is gold. Offering to trace through your code signals confidence and saves you from silent bugs going unnoticed.

Follow-Up Questions (And How to Handle Them)#

A good interviewer won't let you off the hook after the first solution. Here's what they'll throw at you next:

"What if the array has duplicates throughout — does your solution handle that?" Yes, and that's the whole point of the boundary approach. Walk them through the example with [2, 2, 2, 2, 2] — lower bound returns 0, upper bound returns 5, result is [0, 4].

"Can you solve this with a single binary search pass?" Technically yes, but it makes the code significantly more complex and error-prone. Tell them: "I could try to do it in one pass, but the two-function approach is cleaner and still O(log n). The constant factor difference doesn't matter at scale — readability and correctness do." That answer shows engineering maturity.

"How would you adapt this for a rotated sorted array?" This is a classic follow-up pivot. The core insight is that you'd need to first find the rotation point, then decide which half the target lies in. Mention that you'd handle it in two phases — finding the pivot is itself a binary search.

"What's the difference between your lower_bound and what C++ STL provides?" They're identical in concept. std::lower_bound returns an iterator to the first element not less than the target — exactly what our function returns as an index. This is a great moment to show that your solution isn't arbitrary; it mirrors a well-established CS abstraction.

Red Flags to Avoid#

These are the things that make interviewers mentally check a box labeled "not ready":

• Starting to code immediately without pausing to think or clarify. Always spend 60-90 seconds discussing your approach first.
• Writing a linear scan as your first attempt. The problem explicitly says O(log n). If you reach for a loop without binary search, you've already lost points.
• Guessing at boundary conditions instead of reasoning through them. If you can't explain why you wrote r = mid instead of r = mid - 1, that's a red flag.
• Staying silent when stuck. If you hit a wall, say so: "I'm second-guessing my termination condition here — let me trace through a small example to verify." That's a green flag, not a red one.
• Not testing your code after writing it. Always walk through at least one example — especially the edge cases like an empty array or a target at the boundaries.

Key Takeaways#

Here's what you need to walk into your interview knowing cold:

• Reframe the problem: Don't think "first and last occurrence" — think "lower bound and upper bound".
• One character matters: The only difference between lower bound (<) and upper bound (<=) is a single operator. Know which is which and why.
• Upper bound needs a -1: upperBound() returns the first index after the target. Your end index is upperBound - 1.
• Always validate existence: Binary search will return some index even if the target doesn't exist. Check nums[start] == target before returning.
• Use half-open intervals consistently: Initializing r = nums.length (not nums.length - 1) and using l < r as your loop condition avoids a whole class of off-by-one bugs.
• Say the magic words: Opening with "I'll use lower bound and upper bound to avoid edge case bugs" signals pattern recognition and earns immediate credibility.

Binary search is one of those topics where knowing the pattern cold is the difference between breezing through and freezing up. Put in the reps now, and this problem becomes one you look forward to seeing in an interview.