Binsearch C语言如何高效实现？

二分查找是一种非常高效的查找算法,其核心思想是“分治”，它要求数据在查找前必须是有序的（通常是升序排列）。

核心思想

想象一下你在字典里找一个单词：

1. 你不会从第一页开始一页一页翻,而是直接翻到字典的中间。
2. 比较你翻到的单词和你想找的单词：
   • 如果中间的单词正好是你找的,恭喜你，找到了！
   • 如果中间的单词比你找的字母靠后,说明你要找的单词肯定在前半部分，于是你把注意力集中在字典的前半部分，并重复上述过程（翻到前半部分的中间）。
   • 如果中间的单词比你找的字母靠前,说明你要找的单词肯定在后半部分，于是你把注意力集中在字典的后半部分，并重复上述过程。

二分查找就是模仿这个过程,每次都将查找范围缩小一半，因此效率极高。

算法步骤

假设在一个升序排列的数组 arr 中查找目标值 target：

1. 初始化指针：设置两个指针，left 指向数组的起始位置（索引 0），right 指向数组的末尾位置（索引 size - 1）。
2. 循环查找：在 left 指针不大于 right 指针的条件下，执行循环。
3. 计算中间位置：在每次循环中，计算中间位置的索引 mid，为了避免潜在的整数溢出，推荐使用 mid = left + (right - left) / 2 而不是 mid = (left + right) / 2。
4. 比较与缩小范围：
   • arr[mid] == target，说明找到了，返回 mid。
   • arr[mid] < target，说明 target 在 mid 的右侧，所以将 left 指针移动到 mid + 1 的位置。
   • arr[mid] > target，说明 target 在 mid 的左侧，所以将 right 指针移动到 mid - 1 的位置。
5. 结束循环：如果循环结束了（left > right），说明 target 不在数组中，返回一个特殊值（通常是 -1）表示未找到。

C 语言实现

下面是一个完整的 C 语言实现，包含了详细的注释。

1 基础实现（查找单个元素）

这是最标准、最常用的二分查找实现。

#include <stdio.h>
/**
 * @brief 在一个升序数组中进行二分查找
 * 
 * @param arr 有序数组
 * @param size 数组大小
 * @param target 要查找的目标值
 * @return int 如果找到，返回目标值的索引；如果未找到，返回 -1
 */
int binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    // 循环条件，当 left 超过 right 时，说明查找范围已无效
    while (left <= right) {
        // 计算中间索引，使用 left + (right - left) / 2 可以防止 (left + right) 溢出
        int mid = left + (right - left) / 2;
        // 情况1：找到了目标
        if (arr[mid] == target) {
            return mid;
        }
        // 情况2：目标在右半部分
        else if (arr[mid] < target) {
            left = mid + 1; // 缩小查找范围到 [mid+1, right]
        }
        // 情况3：目标在左半部分
        else { // arr[mid] > target
            right = mid - 1; // 缩小查找范围到 [left, mid-1]
        }
    }
    // 循环结束仍未找到，说明目标不存在于数组中
    return -1;
}
int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target1 = 23;
    int target2 = 50;
    // 查找 target1
    int result1 = binarySearch(arr, size, target1);
    if (result1 != -1) {
        printf("元素 %d 在数组中的索引是: %d\n", target1, result1);
    } else {
        printf("元素 %d 不在数组中，\n", target1);
    }
    // 查找 target2
    int result2 = binarySearch(arr, size, target2);
    if (result2 != -1) {
        printf("元素 %d 在数组中的索引是: %d\n", target2, result2);
    } else {
        printf("元素 %d 不在数组中，\n", target2);
    }
    return 0;
}

输出：

元素 23 在数组中的索引是: 5
元素 50 不在数组中。

2 查找边界（第一个等于目标值的元素）

我们不仅要找到一个目标值,还要找到它第一次出现的位置，在数组 [1, 2, 2, 2, 3] 中查找 2，我们希望返回索引 1。

#include <stdio.h>
/**
 * @brief 查找有序数组中第一个等于 target 的元素的索引
 * 
 * @param arr 有序数组
 * @param size 数组大小
 * @param target 目标值
 * @return int 找到则返回索引，未找到返回 -1
 */
int findFirstOccurrence(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    int result = -1; // 用于记录找到的索引
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;       // 记录找到的位置
            right = mid - 1;    // 继续向左查找，看是否有更早的出现
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}
int main() {
    int arr[] = {1, 2, 2, 2, 3, 4, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 2;
    int index = findFirstOccurrence(arr, size, target);
    if (index != -1) {
        printf("元素 %d 第一次出现的索引是: %d\n", target, index);
    } else {
        printf("元素 %d 不在数组中，\n", target);
    }
    return 0;
}

输出：

元素 2 第一次出现的索引是: 1

3 查找边界（最后一个等于目标值的元素）

同理,我们可以查找最后一个等于目标值的元素，在数组 [1, 2, 2, 2, 3] 中查找 2，我们希望返回索引 3。

#include <stdio.h>
/**
 * @brief 查找有序数组中最后一个等于 target 的元素的索引
 * 
 * @param arr 有序数组
 * @param size 数组大小
 * @param target 目标值
 * @return int 找到则返回索引，未找到返回 -1
 */
int findLastOccurrence(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    int result = -1; // 用于记录找到的索引
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;      // 记录找到的位置
            left = mid + 1;    // 继续向右查找，看是否有更晚的出现
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}
int main() {
    int arr[] = {1, 2, 2, 2, 3, 4, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 2;
    int index = findLastOccurrence(arr, size, target);
    if (index != -1) {
        printf("元素 %d 最后一次出现的索引是: %d\n", target, index);
    } else {
        printf("元素 %d 不在数组中，\n", target);
    }
    return 0;
}

输出：

元素 2 最后一次出现的索引是: 3

算法分析

• 时间复杂度：O(log n)，每次循环都将查找范围减半，所以查找次数是 log₂(n) 级别，这比线性查找的 O(n) 快得多，尤其是在数据量很大的时候。
• 空间复杂度：O(1)，我们只使用了固定数量的变量（left, right, mid），没有使用额外的存储空间，因此是常数空间。

注意事项

1. 数据必须有序：二分查找的前提是数组已经是有序的，如果数组无序，必须先进行排序，但排序的代价（通常是 O(n log n)）可能已经超过了二分查找带来的好处。
2. 数据结构限制：二分查找要求数据能够随机访问（Random Access），即可以通过索引在 O(1) 时间内访问任意元素，它主要用于数组，对于链表等数据结构，因为无法高效地计算中间节点，所以不适用。
3. 处理重复元素：基础版本的二分查找在遇到重复元素时，返回的是任意一个匹配元素的索引，如果需要找到第一个或最后一个，需要使用上面提到的边界查找方法。
4. 整数溢出：在计算 mid 时，left 和 right 都非常大（例如接近 INT_MAX），left + right 可能会发生整数溢出，使用 mid = left + (right - left) / 2 是一个更安全、更健壮的写法。