The challenge
Return [first index, last index, count] for a target in a sorted array. If absent, return [−1, −1, 0].
Ascending order with duplicates. Empty input returns [−1, −1, 0].
Example
[1, 2, 2, 2, 5, 8], target = 2 → [1, 3, 3].
Use the walkthrough below to inspect the input and each state change.
See Equal range & count, step by step
Inspect the comparison, the invariant, and the next boundary.
Inclusive candidate indicestarget = 2
Current comparisonResolved positionNumbers below = indices
- Left
- 0
- Middle
- —
- Right
- 5
Step 01 / 11
Find the first value ≥ target
Reset the inclusive candidate interval. The returned boundary is allowed to equal the array length.
left = 0; right = 5Recorded result so far
Not resolved
View exact input
Input: [1,2,2,2,5,8] · target = 2
Put it into code
Run lower bound and upper bound independently. Their half-open interval contains exactly the target’s occurrences.
Indices are zero-based. C++ uses C++17 or later.
def equal_range(nums, target):
def boundary(strict):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target or (strict and nums[mid] == target):
left = mid + 1
else:
right = mid - 1
return left
first, end = boundary(False), boundary(True)
if first == end:
return [-1, -1, 0]
return [first, end - 1, end - first] # First, last, count.#include <array>
#include <vector>
std::array<int, 3> equal_range(const std::vector<int>& nums, int target) {
auto boundary = [&](bool strict) {
int left = 0, right = static_cast<int>(nums.size()) - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target || (strict && nums[mid] == target))
left = mid + 1;
else right = mid - 1;
}
return left;
};
int first = boundary(false), end = boundary(true);
if (first == end) return {-1, -1, 0};
return {first, end - 1, end - first};
}