搜索算法 之 二分搜索（Binary Search）

搜索算法 之 二分搜索（Binary Search）

1. 基础概念

1.1 二分搜索的定义

二分搜索是一种在有序集合中查找目标元素的高效方法。通过每次比较目标值与集合的中间值，决定下一步搜索的方向：若目标值小于中间值，则搜索左半部分；否则搜索右半部分。该过程递归或迭代，直至找到目标或搜索范围为空。

1.2 二分搜索的特点

• 适用于已排序的数组或序列。
• 时间复杂度低（O(log n)），对于大规模数据集效率极高。
• 需要随机访问支持（如数组），不适用于链表。
• 实现简单，递归和迭代版本都容易理解。

1.3 使用场景

• 在有序数组中查找元素是否存在。
• 查找满足特定条件的元素（如最小值、最大值）。
• 优化问题，如在单调函数中查找特定解。

2. 实现与操作

2.1 核心操作实现

以下是使用 C语言 实现二分搜索的代码，包含详细注释和示例：

#include <stdio.h> // 二分搜索函数 // 输入：已排序数组 arr，数组大小 size，目标值 target // 返回：目标值在数组中的索引（若找到），否则返回 -1 int binarySearch(int arr[], int size, int target) { int left = 0, right = size - 1; while (left <= right) { // 计算中间索引，避免溢出 int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; // 找到目标值 } else if (arr[mid] < target) { left = mid + 1; // 搜索右半部分 } else { right = mid - 1; // 搜索左半部分 } } return -1; // 未找到目标值 } int main() { // 示例数组（已排序） int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; int size = sizeof(arr) / sizeof(arr[0]); int target = 7; // 调用二分搜索 int result = binarySearch(arr, size, target); // 输出结果 if (result != -1) { printf("目标值 %d 在索引 %d\n", target, result); } else { printf("目标值 %d 未找到\n", target); } return 0; } </stdio.h>

2.2 代码详解

该代码逻辑清晰：

• 定义搜索范围：通过变量 left 和 right 表示。
• 计算中间索引：避免整数溢出，使用 left + (right - left) / 2。
• 更新搜索范围：根据目标值与中间值的比较结果调整。

3. 时间与空间复杂度分析

3.1 时间复杂度

二分搜索的时间复杂度为 O(log n)，每次搜索范围缩小一半，搜索次数为 log₂(n)。

3.2 空间复杂度

空间复杂度为 O(1)，仅使用常数级额外空间。递归实现的空间复杂度为 O(log n)（递归栈）。

4. 优缺点与局限性

4.1 优点

• 时间效率高，适合大规模数据。
• 实现简单且易于维护。

4.2 缺点与局限性

• 仅适用于有序数组。
• 不适合动态数据集合（如频繁插入或删除）。

5. 常见应用场景

5.1 实际应用

以下示例展示了如何使用二分搜索查找最小满足条件的值：

#include <stdio.h> // 查找第一个大于等于 target 的值的索引 int lowerBound(int arr[], int size, int target) { int left = 0, right = size; while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] < target) { left = mid + 1; // 排除左侧 } else { right = mid; // 保留中间和右侧 } } return left; } int main() { int arr[] = {1, 3, 5, 7, 9, 11}; int size = sizeof(arr) / sizeof(arr[0]); int target = 6; int result = lowerBound(arr, size, target); printf("第一个大于等于 %d 的值位于索引 %d\n", target, result); return 0; } </stdio.h>

6. 代码编译与运行

6.1 编译命令

使用以下命令编译并运行代码：

gcc binary_search.c -o binary_search && ./binary_search

6.2 测试用例

• 输入数组：{1, 3, 5, 7, 9, 11}
• 目标值：6
• 输出结果：第一个大于等于 6 的值位于索引 3