30403：二分上界

题目

在非递减数组中查找第一个严格大于 target 的下标。

解析

维护左闭右开区间 [left, right)，并保持 [0, left) 中的元素都不大于目标值，[right, count) 中的元素都严格大于目标值。中间位置使用 left + (right - left) / 2，避免 left + right 溢出。

遇到 items[middle] <= target 时排除中间位置及其左侧，否则保留中间位置作为答案。

答案

#include <stddef.h>
#include <stdint.h>

size_t upper_bound_i64(
    const int64_t *items,
    size_t count,
    int64_t target
) {
    size_t left = 0;
    size_t right = count;
    while (left < right) {
        size_t middle = left + (right - left) / 2;
        if (items[middle] <= target) {
            left = middle + 1;
        } else {
            right = middle;
        }
    }
    return left;
}

循环结束时 left == right，它就是第一个大于目标的位置；时间复杂度为 $O(\log n)$，额外空间为 $O(1)$。