Mdr-C-Tutorial

主题

30401：二分下界 ​

题目 ​

在非递减数组中查找第一个不小于 target 的元素位置。不存在时返回数组长度。

解析 ​

维护左闭右开区间 [left, right)，并保持：

text
[0, left) 中的元素都小于 target
[right, count) 中的元素都大于等于 target

初始时两个区间都为空，所以不变式成立。每轮取：

c
middle = left + (right - left) / 2;

若中间元素小于目标值，则它和左侧元素都不可能成为答案，将 left 更新为 middle + 1；否则将 right 更新为 middle，保留中间位置作为候选。

解析 ​

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

size_t lower_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;
}

来源与改编 ​

题型改编自 Exercism C Track 的 Binary Search，采用 MIT 许可。本题把精确匹配扩展为下界语义，并增加不变式证明要求，完整说明见习题来源与许可。