templates/upper-bound.cpp
compilable
$cat templates/upper-bound
Upper Bound
Find the last element < target in a sorted array using binary search.
#binary-search#upper-bound#predicate
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
#include <bits/stdc++.h>
using namespace std;
int upperBound(vector<int>& a, int target) {
int l = 0, r = (int)a.size() - 1, ans = -1;
while (l <= r) {
int m = l + (r - l) / 2;
if (a[m] < target) {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
return ans;
}16 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)
Upper Bound (Predecessor)
Finds the last element strictly less than the target in a sorted array.
Important
This is NOT the same as std::upper_bound (which returns first element target). This returns the predecessor — the last element target.