← C++ roadmap

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.

  1. Search [lo,hi).
  2. Use lo+(hi-lo)/2.
  3. Retain >= target on the right.
  4. 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?
Practise C++ with the AI mentor

Can't find a C++ topic you need for exams or placements? Request it and we'll add it.