Find First and Last Position of Element in Sorted Array

Pattern: Binary Search (Leftmost / Rightmost Boundary)
Difficulty: Medium
Key Concept: Run two separate binary searches: one for the first index with value target, one for the last.

Problem Statement

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

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

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

Input: int[] nums, int target
Output: int[] of length 2 — [firstIndex, lastIndex] or [-1, -1]

1. Algorithm & Pseudocode

Brute force

first = -1, last = -1
for i from 0 to nums.length - 1:
    if nums[i] == target:
        if first == -1: first = i
        last = i
return [first, last]

Optimal

function findFirst(nums, target):
    left = 0, right = nums.length - 1, ans = -1
    while left <= right:
        mid = left + (right - left) / 2
        if nums[mid] == target:
            ans = mid
            right = mid - 1   // keep searching left for earlier equal
        else if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return ans

function findLast(nums, target):
    left = 0, right = nums.length - 1, ans = -1
    while left <= right:
        mid = left + (right - left) / 2
        if nums[mid] == target:
            ans = mid
            left = mid + 1    // keep searching right for later equal
        else if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return ans

return [findFirst(...), findLast(...)]

2. Step-by-Step Analysis (Beginner-Friendly)

Why one binary search is not enough
A single standard search might land on any occurrence in the duplicate run. You need the extremes of that run.
Leftmost search
When nums[mid] == target, treat mid as a candidate answer, then discard the right half (right = mid - 1) to see if an equal value exists further left.
Rightmost search
When nums[mid] == target, record mid and discard the left half (left = mid + 1) to see if an equal value exists further right.
If target is absent
Both helpers never update ans from -1, so you return [-1, -1].
Arrays.binarySearch caveat
The JDK does not guarantee which duplicate index you get on a hit; for ranges you still need explicit lower/upper-style logic (or two custom searches).

3. The Dry Run

Input: nums = [5, 7, 7, 8, 8, 10], target = 8
Indices: 0 1 2 3 4 5
Expected: first 8 at 3, last at 4 → [3, 4].

`findFirst` (leftmost 8)

Step	`left`	`right`	`mid`	`nums[mid]`	`ans`	Action
init	0	5	—	—	-1
1	0	5	2	7	-1	`7 < 8` → `left = 3`
2	3	5	4	8	4	`==` → `ans = 4`, `right = 3`
3	3	3	3	8	3	`==` → `ans = 3`, `right = 2`
4	3	2	—	—	3	`left > right` → return 3

`findLast` (rightmost 8)

Step	`left`	`right`	`mid`	`nums[mid]`	`ans`	Action
init	0	5	—	—	-1
1	0	5	2	7	-1	`7 < 8` → `left = 3`
2	3	5	4	8	4	`==` → `ans = 4`, `left = 5`
3	5	5	5	10	4	`10 > 8` → `right = 4`
4	5	4	—	—	4	`left > right` → return 4

Result: [3, 4].

4. Java Solution

Brute Force

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = -1;
        int 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 };
    }
}

Time: O(n). Space: O(1) excluding output.

Optimal

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = findFirst(nums, target);
        if (first == -1) {
            return new int[] { -1, -1 };
        }
        int last = findLast(nums, target);
        return new int[] { first, last };
    }

    private int findFirst(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                ans = mid;
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }

    private int findLast(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                ans = mid;
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

Time: O(log n) for two passes. Space: O(1).

5. The “Java vs. Others” Edge

C++ pairing: std::lower_bound finds first >= target; std::upper_bound finds first > target. For value target, last index is upper_bound - 1 (if in range). Java has no direct STL twins; custom helpers mirror that behavior.
JDK Arrays.binarySearch: On duplicates, behavior is unspecified for which index is returned — do not rely on it for range endpoints.
Same overflow note: use left + (right - left) / 2 for int mids on large arrays.

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n)	O(1)	Two pointers in one scan.
Optimal	O(log n)	O(1)	Two binary searches; independent of duplicate span length.

Find First and Last Position of Element in Sorted Array (LC 34)