Medium · Dual Boundary Search
Understand → Visualise → Practice.
Return the first and last indices of target in a sorted array, or `[-1,-1]`.
The first position of target is lower_bound(target); the last is lower_bound(target + 1) − 1. Both are standard O(log n) boundary searches.
Find the first index whose value is ≥ x, using a half-open [lo, hi) range.
left = lower_bound(target), right = lower_bound(target + 1) − 1.
If left is past the end or nums[left] ≠ target, return [−1, −1].
O(log n) time and O(1) space.
Finding one occurrence and then scanning outwards is O(n) when the target repeats many times.
Read the full guides first: Sorting Algorithms and Their Trade-offs, Binary Search and Boundary Finding.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.