MediumArrayBinary Search

Find First and Last Position of Element in Sorted Array

1 approach, code in every language

You are given an array of integers sorted in non-decreasing order along with a target value. Because the array can contain repeated numbers, the target may occupy a contiguous block of positions. Your job is to report the smallest index and the largest index at which the target appears.

If the target is not present anywhere in the array, return the pair [-1, -1]. The solution is expected to run in logarithmic time, so a straight linear scan does not meet the intended bound.

Example 1

Input: nums = [2, 4, 4, 4, 7, 9], target = 4

Output: [1, 3]

The value 4 first shows up at index 1 and last shows up at index 3, so the answer spans that range.

Example 2

Input: nums = [2, 4, 4, 4, 7, 9], target = 5

Output: [-1, -1]

The value 5 never appears in the array, so there is no valid range and we return [-1, -1].

Constraints

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums is sorted in non-decreasing order
-10^9 <= target <= 10^9

Two Boundary Binary Searches

Run one binary search to locate the leftmost occurrence and another to locate the position just past the rightmost occurrence.

Loading animation…

Intuition

A single lower-bound routine that finds the first index whose value is at least a given key is enough to solve the whole problem. Calling it with the target gives the start of the block. Calling it with target + 1 gives the first index strictly greater than the target, and stepping back one place from there lands on the end of the block. Reusing the same helper twice keeps the logic small and avoids off-by-one mistakes from writing two subtly different searches.

Algorithm walkthrough

1Write a lowerBound helper that returns the first index i where nums[i] >= key using a half-open [lo, hi) search.
2Compute start = lowerBound(target); this is the candidate first position.
3If start is out of bounds or nums[start] does not equal target, the value is absent, so return [-1, -1].
4Compute end = lowerBound(target + 1) - 1, which is the last index still equal to target.
5Return [start, end].

Implementation

from typing import List


class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def lower_bound(key: int) -> int:
            lo, hi = 0, len(nums)
            while lo < hi:
                mid = (lo + hi) // 2
                if nums[mid] < key:
                    lo = mid + 1
                else:
                    hi = mid
            return lo

        start = lower_bound(target)
        if start == len(nums) or nums[start] != target:
            return [-1, -1]
        end = lower_bound(target + 1) - 1
        return [start, end]

Time

O(log n)

Space

O(1)

Two binary searches over n elements, each doing constant extra work.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

After the pattern

Now solve one you haven't seen.

Deviation Value Span is our own problem on the technique behind Find First and Last Position of Element in Sorted Array: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free