Classic / boundaries (Binary Search Sub-pattern)

// First index i where ok(i) is true, for answers shaped false...false true...true.
// Returns n if no index works. Example ok: nums[i] >= target (= lower bound / insert position).
int firstTrue(vector<int>& nums, int target) {
    auto ok = [&](int i) { return nums[i] >= target; };
    int lo = 0, hi = (int)nums.size();     // hi = n means "none of them"
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (ok(mid)) hi = mid;             // mid works: the first true is mid or to its left
        else lo = mid + 1;                 // mid fails: the first true is right of mid
    }
    return lo;                             // lo == hi: the boundary
}