Back to main article
LC 34 First True + Last True Medium

Find First and Last Position of Element in Sorted Array

Two binary searches — one for the left boundary, one for the right. The key insight: run the same template twice with different conditions.

Problem

What are we solving?

Problem Statement

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]
Example 2 — target not found
Input:nums = [5, 7, 7, 8, 8, 10], target = 6
Output:[-1, -1]
Intuition

Two passes: First True then Last True

This problem is really asking two separate questions:

If the element at the left boundary equals the target, the range [left, right] is the answer. If it doesn't equal the target, the target is not present and we return [-1, -1].

Array: [5, 7, 7, 8, 8, 10] · target = 8
Pass 1 — First True: nums[i] >= 8
5>=8?F
7>=8?F
7>=8?F
8>=8?T*
8>=8?T
10>=8?T
First T = index 3. Left boundary of 8 found.
Array: [5, 7, 7, 8, 8, 10] · target = 8
Pass 2 — Last True: nums[i] <= 8
5<=8?T
7<=8?T
7<=8?T
8<=8?T
8<=8?T*
10<=8?F
Last T = index 4. Right boundary of 8 found. Answer: [3, 4].
→

Detecting "target not present": After finding the left boundary, check nums[leftBoundary] == target. If this is false, the target doesn't exist and both boundaries return -1. This single check handles all "not found" cases.

Walkthrough for left boundary

Array: [5, 7, 7, 8, 8, 10], target = 8

1
left=0, right=5 → mid=2, nums[2]=7

7 >= 8? No → FALSE. Search right: left = 3.

2
left=3, right=5 → mid=4, nums[4]=8

8 >= 8? Yes → TRUE. Save boundary=4, search left: right = 3.

3
left=3, right=3 → mid=3, nums[3]=8

8 >= 8? Yes → TRUE. Save boundary=3, search left: right = 2.

4
left=3 > right=2 → loop ends

Left boundary = 3. nums[3] = 8 = target → target exists.

Solution

Two binary searches, one helper

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

    // First True: find first index where nums[i] >= target
    private int findFirst(int[] nums, int target) {
        int left = 0, right = nums.length - 1, boundary = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                boundary = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        // Confirm target actually exists at the boundary
        if (boundary == -1 || nums[boundary] != target) return -1;
        return boundary;
    }

    // Last True: find last index where nums[i] <= target
    private int findLast(int[] nums, int target) {
        int left = 0, right = nums.length - 1, boundary = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                boundary = mid;
                left = mid + 1; // search right for a later match
            } else {
                right = mid - 1;
            }
        }

        return boundary;
    }
}
class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        left = self.find_first(nums, target)
        if left == -1:
            return [-1, -1]
        return [left, self.find_last(nums, target)]

    def find_first(self, nums, target):
        # First True: find first index where nums[i] >= target
        left, right, boundary = 0, len(nums) - 1, -1

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] >= target:
                boundary = mid
                right = mid - 1
            else:
                left = mid + 1

        # Confirm target actually exists at the boundary
        if boundary == -1 or nums[boundary] != target:
            return -1
        return boundary

    def find_last(self, nums, target):
        # Last True: find last index where nums[i] <= target
        left, right, boundary = 0, len(nums) - 1, -1

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] <= target:
                boundary = mid
                left = mid + 1  # search right for a later match
            else:
                right = mid - 1

        return boundary

Complexity

Time
O(log n)
Two binary searches, each O(log n). The constant factor of 2 drops out.
Space
O(1)
No auxiliary structures — just pointer variables.
→

Library connection: find_first is equivalent to bisect_left in Python and lower_bound in C++. find_last is equivalent to bisect_right - 1 and upper_bound - 1. This problem is exactly what those standard library functions implement.

↑ Pattern map