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
01
02
03
04
05
06
07
08
09
10
11
12
#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;
}12 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.