Find First and Last Position of Element in Sorted Array

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Given an array of integers sorted in non-decreasing order and a target value, return the first and last index at which the target appears, as [first, last]. If the target isn't in the array, return [-1, -1]. The solution must run in O(log n) time.

    The best test of whether you can write a binary search that finds a boundary, not just "some match". Original problem: LeetCode 34.

    Example

    The 4s occupy indexes 1 to 3. A target that isn't present, like 5, gives [−1, −1].
    The 4s occupy indexes 1 to 3. A target that isn't present, like 5, gives [−1, −1].
    Input:  nums = [2, 4, 4, 4, 7, 9], target = 4   ->  [1, 3]
    Input:  nums = [2, 4, 4, 4, 7, 9], target = 5   ->  [-1, -1]
    Input:  nums = [2, 4, 4, 4, 7, 9], target = 9   ->  [5, 5]
    Input:  nums = [], target = 3                   ->  [-1, -1]

    Constraints (assumed)

    • 0 ≤ n ≤ 10⁵; values are 32-bit integers; the array is sorted ascending.

    What this question tests

    • A binary search for the first position where a condition becomes true (lower bound).
    • Reusing one helper instead of writing two slightly different searches.
    • Bounds: empty arrays, targets outside the range, and loop termination.

    Questions to ask first

    1. Is the array sorted ascending, with duplicates allowed? (Here: yes.)
    2. What to return when the target is missing? (Here: [-1, -1].)
    3. Is O(log n) required? (Here: yes; a linear scan is not accepted.)
    4. Can I use the library (bisect, lower_bound, Arrays.binarySearch)? Often allowed after you've shown you can write it.