4. 查找与选择

习题

#30401

⚡3⏳2

实现有序数组的二分下界查找：

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

size_t lower_bound_i64(
    const int64_t *items,
    size_t count,
    int64_t target
);

items 按非递减顺序排列。函数返回第一个满足 items[i] >= target 的下标；若不存在，则返回 count。count 为 0 时应返回 0，此时 items 可以为 NULL。

要求使用左闭右开的搜索区间，不得用 left + right 计算中点，并说明循环不变式与 $O(\log n)$ 时间复杂度。

#30403

⚡2⏳2

在 30401 的基础上实现有序数组的二分上界查找：

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

size_t upper_bound_i64(
    const int64_t *items,
    size_t count,
    int64_t target
);

items 按非递减顺序排列。函数返回第一个满足 items[i] > target 的下标；若不存在，则返回 count。

要求使用左闭右开的搜索区间，处理中间位置计算的溢出风险，并说明循环不变式与 $O(\log n)$ 时间复杂度。

#30402

⚡4⏳3

有若干台机器并行生产同一种产品。第 i 台机器每生产一件产品需要 machine_times[i] 个时间单位。实现：

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

bool minimum_production_time(
    const uint64_t *machine_times,
    size_t machine_count,
    uint64_t target,
    uint64_t *out_time
);

要求：

1. 返回生产至少 target 件产品所需的最短时间。
2. target 为 0 时结果为 0，此时机器数组可以为空。
3. target 大于 0 时至少有一台机器，并且每个生产时间都必须大于 0。
4. 不能通过“最慢或最快机器耗时乘以目标件数”直接构造可能溢出的上界。
5. 累加各机器产量时不得溢出；达到目标后应立即停止累加。
6. 参数无效或答案不能用 uint64_t 表示时返回 false，并保持输出对象不变。
7. 使用答案二分，时间复杂度为 $O(m\log T)$，其中 $m$ 为机器数量，$T$ 为答案。

#30404

⚡4⏳3

实现有序统计选择：给定可修改的整数数组和从 0 开始的 order，返回排序后下标为 order 的元素：

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

bool select_kth_i64(
    int64_t *items,
    size_t count,
    size_t order,
    int64_t *out_value
);

要求：

1. order < count；数组可以原地重排，但调用方必须在接口说明中看到这一点。
2. 重复元素必须正确处理；不得使用 int64_t 相减来比较大小。
3. 参数无效时返回 false，不得修改数组和输出对象。
4. 使用分区逐步缩小搜索区间，平均时间复杂度为 $O(n)$，并分析最坏情况。