Introduction

When a vector is sorted in descending order, ordinary binary-search intuition needs to be flipped. To find the first element strictly less than a key, you want the leftmost position where the descending sequence drops below that key.

This is a good fit for binary search because the predicate changes only once. Elements before the answer are greater than or equal to the key, and elements from the answer onward are strictly less than the key.

The Search Condition

Suppose the vector is:

[9, 7, 7, 5, 3, 1]

and the key is 6. The answer is index 3, which holds 5. Everything before index 3 is greater than or equal to 6, and everything from index 3 onward is less than 6.

That monotonic split is exactly what binary search needs.

A Direct Binary Search Solution

Here is a C++ implementation that returns the index of the first element strictly less than key, or -1 if no such element exists:

1#include <iostream>
2#include <vector>
3
4int first_strictly_less_desc(const std::vector<int>& v, int key) {
5    int left = 0;
6    int right = static_cast<int>(v.size()) - 1;
7    int answer = -1;
8
9    while (left <= right) {
10        int mid = left + (right - left) / 2;
11
12        if (v[mid] < key) {
13            answer = mid;
14            right = mid - 1;  // look for an earlier valid position
15        } else {
16            left = mid + 1;   // still too large, move right
17        }
18    }
19
20    return answer;
21}
22
23int main() {
24    std::vector<int> v{9, 7, 7, 5, 3, 1};
25    std::cout << first_strictly_less_desc(v, 6) << '\n';
26    std::cout << first_strictly_less_desc(v, 0) << '\n';
27}

The logic is easy to miss at first because the data is descending. If v[mid] < key, then mid is a valid answer, but there may be an earlier valid index, so search left. Otherwise, the answer must be to the right.

Why This Works

The invariant is:

• indices before the answer contain values >= key,
• the answer and everything after it contain values < key.

Binary search keeps shrinking the range until it isolates the first place where that transition happens.

This gives:

• time complexity O(log n),
• space complexity O(1).

That is much better than a linear scan when the vector is large and you need to answer many queries.

Using std::lower_bound with a Comparator

You can also solve the problem with the standard library, but you need to be careful because the data is descending.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6    std::vector<int> v{9, 7, 7, 5, 3, 1};
7    auto it = std::upper_bound(v.begin(), v.end(), 6, std::greater<int>());
8
9    if (it != v.end()) {
10        std::cout << "Index: " << (it - v.begin()) << ", value: " << *it << '\n';
11    } else {
12        std::cout << "No element strictly less than key\n";
13    }
14}

For many developers, the handwritten binary search is clearer because the intent is explicit. The standard-library version is compact, but it is easier to misuse when the ordering is reversed.

Edge Cases to Handle

There are a few cases worth testing explicitly:

• empty vector,
• key smaller than every element,
• key larger than every element,
• duplicates around the boundary.

For example, with [9, 7, 7, 5] and key 7, the correct answer is the first 5, not one of the 7 entries, because the requirement is strictly less than the key.

Common Pitfalls

• Reusing an ascending-order binary search without reversing the comparison logic.
• Returning the first element less than the key that you happen to find, rather than the leftmost one.
• Mixing up strictly less than with less than or equal to when duplicates exist.
• Forgetting to return -1 when no valid element exists.
• Using the wrong standard-library function with a descending comparator and then trusting the result blindly.

Summary

• The problem is a binary-search boundary search on a descending vector.
• The correct answer is the leftmost index where v[i] < key.
• A direct binary search solves it in O(log n) time and O(1) space.
• Duplicates matter because the comparison is strictly less than, not less than or equal to.
• Standard-library algorithms can work too, but explicit binary search is often easier to reason about here.