深入解析 C 语言中的 lower_bound 与 upper_bound：从二分查找底层原理到高性能实现

你好！作为一名专注于 C 语言性能优化的开发者，你是否曾在处理海量数据时，苦恼于如何在一个已排序的数组中快速定位特定元素的插入位置？

C++ 标准库中提供了 INLINECODEbbc8b31d 和 INLINECODEc8744f07 这两个极其强大的算法，但当我们工作在纯 C 环境或嵌入式系统中时，往往无法直接使用这些便利的工具。在这篇文章中，我们将摒弃对外部库的依赖，一起深入探索如何利用经典的二分查找算法，从零开始实现这两个关键函数。

我们将不仅会展示“如何写代码”，还会深入剖析“为什么这么写”。你将学会如何处理边界条件，如何优化递归与迭代，并掌握在 1,000 万级别的数据面前依然保持高效查找的实战技巧。让我们开始这段探索之旅吧！

问题陈述与核心概念

首先，让我们明确我们要解决什么问题。给定一个长度为 N 的已排序整数数组 arr[] 和一个目标值 K，我们的目标是确定两个特定的位置：

• 下界: 数组中第一个大于或等于 K 的元素的位置。如果所有元素都小于 K，则返回数组末尾的位置（即 N）。
• 上界: 数组中第一个严格大于 K 的元素的位置。如果所有元素都小于等于 K，同样返回 N。

为了让你更直观地理解，让我们看一个具体的例子。

#### 场景示例

假设我们有一个已排序的数组：

arr[] = {4, 6, 10, 12, 18, 20}
情况 A：查找 K = 6

• 我们来找 lower_bound(6)：从左向右扫描，第一个遇到的 6 就是目标。结果：6，索引为 1。
• 我们来找 upper_bound(6)：我们要找比 6 大的数。6 后面的下一个数是 10。结果：10，索引为 2。

情况 B：查找 K = 20

• lower_bound(20)：数组中存在 20，它是第一个大于等于 20 的元素。结果：20，索引为 5。
• upper_bound(20)：数组中没有比 20 更大的数了。这意味着上界不存在（或者说位于数组末尾之后）。在我们的实现中，这通常返回索引 6（即 N）。

核心原理：二分查找的威力

你可能会问，为什么不直接用线性扫描？

如果数组只有 10 个元素，线性扫描确实很快。但在大数据量下（例如 1 亿条数据），线性扫描的时间复杂度是 O(N)，这在实时系统中是不可接受的。而二分查找的时间复杂度是 O(log N)。

让我们算一笔账：

• 对于 1 亿数据，线性扫描平均需要比较 5000 万次。
• 而二分查找只需要比较约 27 次（$log_2(10^8) \approx 26.57$）。

这就是为什么我们坚持使用二分查找的原因。下面，我们将拆解实现这两个函数的具体逻辑。

实战：迭代式实现（推荐方案）

在 C 语言中，相比于递归，迭代实现通常是更优的选择，因为它不会产生额外的函数调用栈开销，且在极端数据量下更不容易导致栈溢出。我们将使用一种特殊的二分查找变体，它维护一个搜索区间 [low, high)（注意 high 是开区间）。

这种左闭右开的区间处理方式是算法设计中的黄金法则，能极大地减少“差一错误”的发生。

#### 代码实现与深度解析

这是一个完整的、可直接运行的 C 语言程序。我添加了详细的中文注释，帮助你理解每一步的逻辑。

#include 

/*
 * 函数: lower_bound
 * 功能: 在已排序数组中查找第一个大于等于 X 的元素的索引
 * 参数:
 *   arr: 已排序的数组
 *   N: 数组长度
 *   X: 目标值
 * 返回值: 目标索引。如果未找到，返回 N
 */
int lower_bound(int arr[], int N, int X)
{
    int mid;

    // 初始化搜索区间为 [0, N)
    // low 是闭区间，high 是开区间
    int low = 0;
    int high = N;

    // 只要区间还有效（low 不等于 high）
    while (low < high) {
        // 防止溢出的写法：mid = low + (high - low) / 2
        // 等同于 (low + high) / 2，但在大数组下更安全
        mid = low + (high - low) / 2;

        // 如果 X 小于等于中间值，说明目标在左半部分（包含 mid）
        // 这里的“<=”是关键：它确保我们不会跳过相等的元素
        if (X <= arr[mid]) {
            high = mid; // 缩小区间到左半边
        }
        // 如果 X 大于中间值，说明目标一定在右半部分（不包含 mid）
        else {
            low = mid + 1; // 缩小区间到右半边
        }
    }

    // 循环结束时，low == high，这就是分界点
    // 为了防止某些特殊情况下的越界（虽然算法逻辑上已涵盖），
    // 我们可以做一个简单的检查，但标准实现通常直接返回 low。
    return low;
}

/*
 * 函数: upper_bound
 * 功能: 在已排序数组中查找第一个严格大于 X 的元素的索引
 * 参数:
 *   arr: 已排序的数组
 *   N: 数组长度
 *   X: 目标值
 * 返回值: 目标索引。如果未找到，返回 N
 */
int upper_bound(int arr[], int N, int X)
{
    int mid;
    int low = 0;
    int high = N;

    while (low = arr[mid]
        // 如果中间元素小于等于 X，我们要找的“严格大于”的元素一定在右边
        // 这意味着我们不仅要丢弃小于 X 的，还要丢弃等于 X 的
        if (X >= arr[mid]) {
            low = mid + 1;
        }
        // 如果中间元素已经大于 X，那它可能就是我们要找的，或者更左边的才是
        else {
            high = mid;
        }
    }

    return low;
}

// 主函数 - 测试用例
int main()
{
    // 测试用例 1：常规情况
    int arr[] = { 4, 6, 10, 12, 18, 20 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int X = 6;

    int l = lower_bound(arr, N, X);
    int u = upper_bound(arr, N, X);

    printf("Lower bound of %d is at index %d (Value: %d)
", X, l, l < N ? arr[l] : -1);
    printf("Upper bound of %d is at index %d (Value: %d)
", X, u, u < N ? arr[u] : -1);

    return 0;
}

进阶：C++ 风格的泛型实现与类型安全

既然我们追求极致的性能和现代开发理念，就不能局限于仅仅处理 INLINECODE3bcbd09c 数组。在 2026 年的今天，即便是在 C 语言项目中，我们也推荐使用 INLINECODEa672d568 和函数指针来实现类似 C++ 模板的泛型编程能力。这不仅能减少代码重复，还能提高代码的可维护性。

让我们来打造一个“生产级”的 lower_bound 实现，它能够处理任意类型的数据，并允许自定义比较逻辑。

#include 
#include 

// 定义一个比较函数指针类型
// 返回值: < 0 表示 a  0 表示 a > b
typedef int (*CompareFunc)(const void* a, const void* b);

/*
 * 泛型 lower_bound 实现
 * base: 数组起始地址
 * nmemb: 数组元素个数
 * size: 每个元素的大小（字节）
 * key: 指向目标值的指针
 * compar: 比较函数
 */
void* generic_lower_bound(const void* base, size_t nmemb, size_t size,
                          const void* key, CompareFunc compar)
{
    const char* array = (const char*)base; // 将 void* 转换为字节指针以便进行指针运算
    size_t low = 0;
    size_t high = nmemb;

    while (low < high) {
        // 这里同样注意防止溢出，但这次是在字节级别计算偏移量
        size_t mid = low + (high - low) / 2;
        const void* mid_elem = array + mid * size;

        // 如果 key <= mid_elem，说明结果在左半部分（包含 mid）
        if (compar(key, mid_elem) <= 0) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }

    // 返回计算出的地址，如果越界则返回末尾地址
    return (void*)(array + low * size);
}

// 示例比较函数：整数
int compare_int(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

// 示例比较函数：字符串（字典序）
int compare_str(const void* a, const void* b) {
    return strcmp(*(const char**)a, *(const char**)b);
}

// 测试泛型实现
void test_generic_implementation() {
    // 测试整数数组
    int int_arr[] = { 10, 20, 30, 40, 50 };
    int target_int = 25;
    int* p_int = (int*)generic_lower_bound(int_arr, 5, sizeof(int), &target_int, compare_int);
    printf("Generic Lower Bound for 25 in int array: Index %ld
", p_int - int_arr);

    // 测试字符串数组
    const char* str_arr[] = { "apple", "banana", "cherry", "date" };
    const char* target_str = "blueberry";
    // 字符串数组实际上是指针的数组，所以元素大小是 sizeof(char*)
    const char** p_str = (const char**)generic_lower_bound(str_arr, 4, sizeof(char*), &target_str, compare_str);
    printf("Generic Lower Bound for 'blueberry': Index %ld
", p_str - str_arr);
}