二分查找（Binary Search）

二分查找每次取区间中点元素与目标进行比较，无论结果如何，都能将搜索区间缩小一半，从而在 O(log n) 时间内完成查找。 前提：数组必须有序且支持随机访问（顺序存储结构）。

查找过程

每次取区间 [lo, hi] 的中点 mid = (lo + hi) / 2 进行比较：

• 若 A[mid] = target，查找成功；
• 若 A[mid] < target，在右半区间继续（lo = mid + 1）；
• 若 A[mid] > target，在左半区间继续（hi = mid - 1）；
• 区间为空（lo > hi）则查找失败。

过程模拟

以有序数组 [1, 3, 5, 7, 9, 11, 13]、目标 target = 11 为例：

步骤图：lo=0, hi=6, mid=3，A[3]=7 < 11，令 lo=4

1/2

左右边界与插入点

当数组中存在重复元素，或需要确定插入位置时，需要使用二分的边界变体：

• 左边界查找：找到 target 后不立即返回，令 hi = mid - 1 继续向左收缩，直至区间为空；最终 lo 即为首次出现位置。
• 右边界查找：找到 target 后令 lo = mid + 1 继续向右收缩；最终 hi 即为末次出现位置。
• 插入位置：当 target 不存在时，lo 即为维持有序的应插入位置。

算法特性

• 时间复杂度：O(log n)。每次比较缩小一半，最多比较 ⌈log₂(n+1)⌉ 次。
• 空间复杂度：O(1)。迭代实现只需常数额外空间；递归实现为 O(log n) 栈空间。
• 前提条件：数组必须有序且支持 O(1) 随机访问（不适用链表）。
• 稳定查找：通过边界变体可精确定位重复元素的首次或末次出现位置。

Baseline 任务：二分查找

任务内容

完成 ordered_search.cpp，实现以下函数：

1. 基础二分查找 int BinarySearch(vector<int>& nums, int target)
   • 在有序表中查找目标关键字，返回下标或 -1
2. 左边界查找 int BinarySearchLeftBound(vector<int>& nums, int target)
   • 返回 target 首次出现的下标
3. 右边界查找 int BinarySearchRightBound(vector<int>& nums, int target)
   • 返回 target 末次出现的下标
4. 插入位置查找 int BinarySearchInsertionPoint(vector<int>& nums, int target)
   • 返回 target 应插入的位置，使数组保持有序

文件结构

• ordered_search.h：函数声明
• ordered_search.cpp：查找算法核心实现
• test.cpp：测试程序

验证方式

• 编译：g++ -std=c++17 test.cpp ordered_search.cpp -o testOrderedSearch
• 运行：./testOrderedSearch