Free lesson · DSA Mastery - Interview Prep, End to End

Find First and Last Position of Element in Sorted Array

Medium7 min readdsabinary-search

Find First and Last Position of Element in Sorted Array

Find First and Last Position of Element in Sorted Array combines both bounds in one problem: locate the first and last index of a target value in a sorted array with duplicates, in O(log n). It's lower bound and upper bound applied together - the first occurrence is the lower bound of the target, and the last occurrence is one position before the upper bound. This makes it the natural culmination of the standard binary search sub-group, tying together the lower-bound (Search Insert Position) and upper-bound (Find Smallest Letter) primitives you just built. We present the linear-scan baseline and the two-boundary-search solution.

The insight: a target's occurrences form a contiguous block in a sorted array. The block starts at the lower bound (first index with value >= target) and ends just before the upper bound (first index with value > target). Two boundary searches pin down both ends in O(log n) total.

The Problem

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input:  nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Explanation: 8 appears at indices 3 and 4.

Example 2:

Input:  nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Explanation: 6 is not in the array.

Example 3:

Input:  nums = [], target = 0
Output: [-1,-1]

Constraints:

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums is a non-decreasing array.
• -10^9 <= target <= 10^9

Approaches Overview

Linear scan finds both ends in one pass - O(n), failing the requirement. The two-boundary approach runs lower bound (first >= target) and upper bound (first > target), deriving the first and last positions in O(log n).

Approach 1: Linear Scan

The Idea

Scan once, recording the first and last index where the value equals the target. If the target never appears, return [-1, -1]. Correct but O(n).

Logic Flowchart

graph TD
    A["first = last = -1"] --> B["for i = 0 .. n-1"]
    B --> C{"nums[i] == target?"}
    C -->|Yes| D["if first==-1 first=i; last=i"]
    C -->|No| E["skip"]
    D --> F{"more?"}
    E --> F
    F -->|Yes| B
    F -->|No| G["return [first, last]"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the linear scan. We record the first and last index where the value equals the target in a single pass, returning negative ones if it never appears.

Complexity

Time: O(n). Space: O(1). Two boundary searches reach O(log n).

Approach 2: Two Boundary Searches - Optimal

The Idea

Run two lower-bound-style searches. The first occurrence is lowerBound(target) - the first index with nums[i] >= target; if that index is in range and equals the target, it's the start, else the target is absent. The last occurrence is lowerBound(target + 1) - 1 - one before the first index with value > target. Each search is O(log n), so the total is O(log n).

Logic Flowchart

graph TD
    A["first = lowerBound(nums, target)"] --> B{"first in range and nums[first]==target?"}
    B -->|No| C["return [-1, -1]"]
    B -->|Yes| D["last = lowerBound(nums, target+1) - 1"]
    D --> E["return [first, last]"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the two-search approach. The first occurrence is the lower bound of the target; if that position does not hold the target, it is absent. The last occurrence is one before the lower bound of target plus one.

Code

public static int[] searchRange(int[] nums, int target) {
    int first = lowerBound(nums, target);
    if (first == nums.length || nums[first] != target) {
        return new int[]{-1, -1};             // target not present
    }
    int last = lowerBound(nums, target + 1) - 1;   // one before first index > target
    return new int[]{first, last};
}

// first index i with nums[i] >= key, or nums.length if none
private static int lowerBound(int[] nums, int key) {
    int lo = 0, hi = nums.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] >= key) hi = mid;        // candidate: keep
        else lo = mid + 1;                     // too small: discard
    }
    return lo;
}

// Usage:
// searchRange([5,7,7,8,8,10], 8) -> [3,4]
// searchRange([5,7,7,8,8,10], 6) -> [-1,-1]

This Java code uses a lower-bound helper. The first occurrence is the lower bound of the target, checked against the target value; the last occurrence is one before the lower bound of the target plus one. Each search is logarithmic.

Step-by-Step Walkthrough

A frame-by-frame trace on nums = [5,7,7,8,8,10], target = 8:

graph LR
    F0["lowerBound(8): first index with value>=8 → index 3 (nums[3]=8)"]
    F1["nums[3]==8 ✓ so first = 3"]
    F2["lowerBound(9): first index with value>=9 → index 5 (nums[5]=10)"]
    F3["last = 5 - 1 = 4"]
    F4["return [3, 4]"]
    F0 --> F1 --> F2 --> F3 --> F4

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F4 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough finds the range of eight in five, seven, seven, eight, eight, ten. The lower bound of eight is index three, which holds eight, so the first position is three. The lower bound of nine is index five, so the last position is four.

Result: [3, 4].

Complexity

Time: O(log n) - two boundary searches. Space: O(1).

Complexity Comparison

The two-search approach is optimal and elegantly reuses a single lowerBound helper for both ends: the start is lowerBound(target) and the end is lowerBound(target + 1) - 1. This reduces a "find a range" problem to two applications of one primitive - the payoff of mastering lower bound.

Variations & Follow-ups

Why is the last occurrence lowerBound(target + 1) - 1?

lowerBound(target + 1) is the first index whose value is at least target + 1, i.e., the first index strictly greater than target - that's the upper bound of target. The target's last occurrence is the position just before it, hence - 1. Using target + 1 lets you reuse the same lower-bound helper instead of writing a separate upper-bound routine (watch for overflow if target could be the max int - use long or a dedicated upper bound then).

Why check nums[first] != target for absence?

lowerBound(target) returns the insertion point even when the target is missing - it points at the first element greater than the target (or n). So you must verify that the position is in range and actually holds the target. If not, the target never appears, and you return [-1, -1] without computing the last position.

Could you do it with one search plus expansion?

You could find any occurrence with a standard search, then linearly expand left and right to the block's ends - but that expansion is O(n) in the worst case (an array of all-equal values), violating the O(log n) requirement. Two boundary searches keep it strictly logarithmic regardless of how many duplicates exist.

How does this connect to counting occurrences?

The count of the target equals last - first + 1, or equivalently upperBound(target) - lowerBound(target). So this problem is the foundation for "how many times does x appear in a sorted array?" - a direct O(log n) answer via two boundary searches, far better than scanning.

What about edge cases?

• Target absent (Example 2): Lower bound points past or at a non-target element → [-1, -1].
• Empty array (Example 3): Lower bound returns 0 == length → [-1, -1].
• Single occurrence: first == last.
• All elements equal the target: Returns [0, n-1].
• Target at the array's end: lowerBound(target + 1) returns n, so last = n - 1.

Common Interview Pitfalls

• Forgetting the presence check. Lower bound returns an insertion point even on a miss; verify nums[first] == target.
• Off-by-one on the last position. It's lowerBound(target + 1) - 1, not lowerBound(target) + count or similar.
• Linear expansion after finding one. Defeats the O(log n) requirement on duplicate-heavy inputs.
• Overflow on target + 1. If target can be Integer.MAX_VALUE, use a separate upper-bound search or wider type.

Why This Topic Matters

Find First and Last Position is the capstone of the standard binary search sub-group: it composes lower and upper bound to answer a range query in O(log n), and it shows how a single well-understood primitive (lowerBound) solves multiple problems by varying its argument. Range-finding and occurrence-counting in sorted data are extremely common, and reducing them to boundary searches is a hallmark of fluent binary search.

This completes the Standard Binary Search sub-group. You built the exact-match template (Binary Search), the boundary template (First Bad Version), binary search on a number line (Valid Perfect Square), lower bound (Search Insert Position), the comparison-oracle view (Guess Number), upper bound with wraparound (Find Smallest Letter), and the composition of both bounds (this problem). Together they cover essentially every "search in sorted data" pattern.

The next sub-group, Modified Binary Search, applies the technique to arrays whose sorted structure has been disrupted - rotated, with peaks, or mountain-shaped. It opens with Search in Rotated Sorted Array: a sorted array rotated at an unknown pivot, where you must still find a target in O(log n). The trick is that even after rotation, at least one half of any subarray is still sorted - so you check which half is sorted, decide whether the target lies within it, and recurse accordingly. It's binary search where each step first identifies the sorted portion before deciding which way to go.

Back to DSA Mastery - Interview Prep, End to End