Find First and Last Position of Element in Sorted Array

MediumBinary Search · Lower / Upper Bound🧩 Binary Search LeetCode #34 ↗Updated Oct 30, 2026

Problem

You get an array nums sorted in non-decreasing order (duplicates allowed) and a target. Return the indices [first, last] of the leftmost and rightmost occurrence of target, or [-1, -1] if it is absent. Aim for O(log n) time.

Input[5,7,7,8,8,10], t=8Output[3,4]

Input[5,7,7,8,8,10], t=6Output[-1,-1]

Input[], t=0Output[-1,-1]

0 ≤ n ≤ 10⁵ · -10⁹ ≤ nums[i], target ≤ 10⁹ · nums is sorted · Required: O(log n).

Try it yourself

Java

class Solution {
    public int[] searchRange(int[] nums, int target) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Don't stop when nums[mid] == target — keep shrinking toward one side. Biasing left on equality finds the first index, biasing right finds the last: two clean O(log n) boundary searches.

PatternBinary Search

Instinct Sorted data, a rotated array, or find the min/max X that works where a yes/no test flips only once - halve the search space every step.

Memory hack Find the fence - every candidate reads NO NO NO YES YES, and binary search just walks to where the fence stands.

Open the Binary Search guide →

Approaches

Brute ForceLinear Scan

Time O(n)Space O(1)

Walk the array once. The first time we see target we record first; every match updates last. Ignores the sorted order entirely.

Java

public int[] searchRange(int[] nums, int target) {
    int first = -1, last = -1;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) {
            if (first == -1) first = i;
            last = i;
        }
    }
    return new int[]{first, last};
}

Trivially correct, but O(n) violates the required O(log n).

BetterBinary Search + Expand Outward

Time O(log n + k)Space O(1)

Run a normal binary search to land on any copy of target, then walk left and right while neighbours still equal it. Fast when the target appears few times, but k copies cost k steps — an all-equal array degrades to O(n).

Java

public int[] searchRange(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid + 1;
        else if (nums[mid] > target) right = mid - 1;
        else {
            int start = mid, end = mid; // expand around the hit
            while (start > 0 && nums[start - 1] == target) start--;
            while (end < nums.length - 1 && nums[end + 1] == target) end++;
            return new int[]{start, end};
        }
    }
    return new int[]{-1, -1};
}

Usually fast, but the expansion makes the worst case linear.

OptimalTwo Boundary Binary Searches

Time O(log n)Space O(1)

findFirst moves right = mid - 1 whenever nums[mid] ≥ target, so left ends on the first index with value ≥ target (lower bound). findLast moves left = mid + 1 whenever nums[mid] ≤ target, so right ends on the last index with value ≤ target. Verify each lands on target.

Java

public int[] searchRange(int[] nums, int target) {
    return new int[]{findFirst(nums, target), findLast(nums, target)};
}
private int findFirst(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) right = mid - 1; // keep going left
        else left = mid + 1;
    }
    return (left < nums.length && nums[left] == target) ? left : -1;
}
private int findLast(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) left = mid + 1; // keep going right
        else right = mid - 1;
    }
    return (right >= 0 && nums[right] == target) ? right : -1;
}

Dry run[5,7,7,8,8,10], t=8

l leftr rightm mid changed

F1
5
l
7

7
m
8

8

10
r
7 < 8 → l=3
F2
5

7

7

8
l
8
m
10
r
8 ≥ 8 → r=3
F3
5

7

7

8
l r m
8

10

8 ≥ 8 → r=2; first=3
L1
5
l
7

7
m
8

8

10
r
7 ≤ 8 → l=3
L2
5

7

7

8
l
8
m
10
r
8 ≤ 8 → l=5
L3
5

7

7

8

8

10
l r m
10 > 8 → r=4; last=4 ✔

Guaranteed O(log n) regardless of how many duplicates exist.

Pro tip

findLast(t) equals findFirst(t + 1) - 1 — one lower-bound helper can answer both.

At a glance

Level	Approach	Time	Space
Brute Force	Linear Scan	`O(n)`	`O(1)`
Better	Binary Search + Expand Outward	`O(log n + k)`	`O(1)`
Optimal	Two Boundary Binary Searches	`O(log n)`	`O(1)`

Common pitfalls

Returning as soon as nums[mid] == target — that's a match, not the boundary.
Skipping the final check — left may be n or point at a different value.
Using (l + r) / 2 — can overflow; prefer l + (r - l) / 2.

Interview tips

Name it: first = lower bound, last = upper bound − 1.
Point out why find-then-expand is O(n) on [8,8,8,...].
Test with empty array, single element, and target smaller/larger than all values.

Pattern

Boundary binary search → sorted data with duplicates and you need the first/last position satisfying a condition.

My notes saved in this browser