← DSA Atlas
Dedicated problem page · #34

Find First and Last Position of Element

MediumBinary SearchLower-bound binary search on both endsTwo binary searches for the first and last occurrence
Solve on LeetCode ↗
34
MediumBinary SearchTwo binary searches for the first and last occurrenceLower-bound binary search on both ends

Find First and Last Position of Element

Given a non-decreasing sorted array nums and a target value, return the starting and ending index of target as [first, last]. If target is not present, return [-1, -1]. You must run in O(log n) time.

Open official problem prompt ↗
In plain English

Report the inclusive index span occupied by a target value in a sorted array, or signal its absence.

Picture it like this

Like finding where a word's entries begin and end in a dictionary: you flip to the first page where it could appear and the first page after it stops, and everything between is that word.

Example
Input
nums = [5, 7, 7, 8, 8, 10], target = 8
Output
[3, 4]
Why
The value 8 first appears at index 3 and last appears at index 4.
Constraints
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9nums is a non-decreasing array-10^9 <= target <= 10^9
Pattern lesson

See the pattern, then code

Lower-bound binary search on both ends
Recognition clue

Asking for the range of a value in a sorted array with duplicates and an O(log n) bound is the signal for lower-bound / upper-bound binary search.

↗
Binary Search

Sorted data or a monotonic true/false condition over a possible answer.. The first index of target equals the lower bound of target, and the last index equals the lower bound of target+1 minus one; two boundary searches pin the whole block.

New words, made simpleKnow these before the algorithm
Lower bound
The first index whose value is >= x; if all values are smaller it equals the array length.
Half-open range
Searching with hi = len(nums) so the answer can legitimately be one past the end.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Linear scan for both ends

Correct but ignores sortedness and misses the log-time bound.

Walk left to right recording first and last match.

Time O(n)Space O(1)
Find one occurrence then expand

Degrades to linear when the value fills most of the array.

Binary-search any match then walk outward to the edges.

Time O(n) worst caseSpace O(1)
Best choiceTwo lower-bound searches

Guaranteed logarithmic regardless of duplicate count.

lower_bound(target) and lower_bound(target+1) delimit the block.

Time O(log n)Space O(1)
The rule we keep true

Invariant

In each lower_bound call, every index < lo has value < x and every index >= hi has value >= x, so lo converges to the first index not less than x.

Why this is correct

Reasoning

lower_bound(target) is by definition the first position where target could be, i.e. its first occurrence if present. lower_bound(target+1) is the first position strictly greater than target, so one less is target's last occurrence. Comparing nums[start] to target detects absence. Both calls are logarithmic.

The algorithm in three movesSay these aloud before coding
1Write a lower_bound helper returning the first index with value >= x

lower_bound(8) -> first index with value>=8 is 3

2Find start = lower_bound(target)

nums[3]=8 matches target

3If start is out of range or nums[start] != target, return [-1, -1]

lower_bound(9) -> 5; end = 5 - 1 = 4 -> return [3,4]

4Find end = lower_bound(target + 1) - 1

5Return [start, end]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
50
71
72
83
84
105
1 · Readtarget = 8
2 · AskFirst index with value >= 8?
3 · Update stateconverges to index 3
4 · Resultstart = 3
Key takeaway

The two 8s occupy indices 3 and 4, bounded by the lower bounds of 8 and 9.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-11Lower-bound helper

    A standard half-open binary search returning the first index whose value is at least x.

  2. 2
    Lines 12-14First occurrence and absence check

    If lower_bound lands past the end or on a different value, target is missing.

  3. 3
    Lines 15-16Last occurrence

    lower_bound(target+1) - 1 is the final index equal to target.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Empty array
  • Target absent but within the value range
  • Target smaller than all or larger than all elements
  • Every element equals target
!

Common beginner mistakes

  • Setting hi = len(nums) - 1, which breaks when target+1 exceeds all values
  • Forgetting the presence check and returning a bogus range for a missing target
  • Handling integer overflow of target+1 (safe in Python but a trap in other languages)
Check your understanding

Why does lower_bound(target + 1) - 1 give the last occurrence?

More in Binary Search

#33Search in Rotated Sorted ArrayBinary search on a rotated array#153Find Minimum in Rotated Sorted ArrayBinary search for the rotation point#875Koko Eating BananasBinary search on the answer#4Median of Two Sorted ArraysBinary search on the partition#35Search Insert PositionLower-bound binary search#74Search a 2D MatrixBinary search on a flattened grid