Topic 23 of 27 · Beginner
Return the first matching index in a sorted vector
Return the first index equal to target or -1 in a nondecreasing integer vector.
BasicEntry level · 0–1 yearsBinary search
C++20; compile with g++ -std=c++20.
Problem statement
Return the first index equal to target or -1 in a nondecreasing integer vector.
A sorted-key lookup needs deterministic duplicate handling.
Input: const vector<int>& and int target.
Output: int index or -1.
- Size <= INT_MAX.
- Sorted ascending with duplicates allowed.
Sample 1
Input: [1,2,2,4],2 Output: 1
Lower bound identifies the first duplicate.
Sample 2
Input: [],2 Output: -1
No valid index exists.
Brute-force solution
Scan the array from the beginning.
O(log n)
#include <vector>
#include <iostream>
#include <cassert>
int lower_match(const std::vector<int>& a,int target){std::size_t lo=0,hi=a.size();while(lo<hi){std::size_t mid=lo+(hi-lo)/2;if(a[mid]<target)lo=mid+1;else hi=mid;}return lo<a.size() && a[lo]==target ? static_cast<int>(lo) : -1;}
int main() {
assert(lower_match({1,2,2,4},2)==1);assert(lower_match({},2)==-1);std::cout<<lower_match({1,2,2,4},2)<<"\n";
return 0;
}
Optimized solution
Use a half-open binary search then check equality at its boundary.
- Search [lo,hi).
- Use lo+(hi-lo)/2.
- Retain >= target on the right.
- Check boundary is in range.
#include <vector>
#include <iostream>
#include <cassert>
int lower_match(const std::vector<int>& a,int target){std::size_t lo=0,hi=a.size();while(lo<hi){std::size_t mid=lo+(hi-lo)/2;if(a[mid]<target)lo=mid+1;else hi=mid;}return lo<a.size() && a[lo]==target ? static_cast<int>(lo) : -1;}
int main() {
assert(lower_match({1,2,2,4},2)==1);assert(lower_match({},2)==-1);std::cout<<lower_match({1,2,2,4},2)<<"\n";
return 0;
}
Complexity analysis
Time: O(log n)
Auxiliary space: O(1)
Test cases
- Empty.
- All duplicates.
- Absent target.
Supplied main asserts first duplicate and empty input.Common mistakes
- Mixing signed -1 with size_t during search.
- Returning insertion index without equality verification.
Key takeaways
- Boundary search handles duplicates.
- Verify the result.
- Respect index range limits.
Follow-up challenges
- How does std::lower_bound express this?
- How do you find an equal range?