C++二分法详解

C++二分法详解

---

一、算法简介

---

二分查找（Binary Search）是一种 高效搜索算法 ，适用于 有序序列 。通过每次将搜索范围减半，时间复杂度为O(log n)。

---

二、算法原理

核心思想(以找到第一个大于等于target的数字为例)

1. 确定搜索区间的初始边界 [left, right]
2. 计算中间位置：

1.mid = (left + right)/2
2.mid = left + (right - left)/2（防溢出写法）

3.比较中间元素与目标值：

• 若 arr[mid] < target → 搜索右半区 [mid+1, right]
• 若 arr[mid] >= target → 搜索左半区 [left, mid]

4.重复直到找到目标或区间无效

---

数学本质：

每次将问题规模缩小为原来的1/2 ；
最多需要 log₂(n) 次迭代；

三、代码实现

---

标准版本（循环实现）

int left = 1, right = arr.size() ;while (left < right) {  // 注意等号int mid = left + (right - left) / 2;  // 防止溢出if (arr[mid] < target) {left = mid + 1;  // 更新左边界} else {right = mid;  // 更新右边界}}//第一个大于等于target的数字位于下标为left的元素上
}

---

四、复杂度分析

• 时间复杂度：O(log n)

---

五、常见练习题

1.在数组中查找元素的第一个和最后一个位置
2.求x的平方根（保留整数部分)
3.在旋转排序数组中找最小值