定义
二分查找（Binary Search）是一种在有序数组中查找目标元素的高效算法。其核心思想是利用数组的有序性，每次将搜索范围缩小一半，从而实现 的时间复杂度。1
二分查找的思想虽然简单，但实现时边界条件的处理容易出错，需要特别注意。
核心特性
时间复杂度
- 时间复杂度： — 每一次比较都将搜索范围缩小一半
- 空间复杂度：（迭代实现）或 （递归实现）
适用条件
二分查找要求：
- 数组必须有序（升序或降序）
- 能够通过索引随机访问（数组，不适用于链表）
- 存在明确的上下界
算法步骤
- 确定搜索范围的左边界
left和右边界right - 计算中点
- 比较
arr[mid]与目标值target：- 若
arr[mid] == target，找到目标，返回mid - 若
arr[mid] < target，目标在右半部分，更新left = mid + 1 - 若
arr[mid] > target，目标在左半部分，更新right = mid - 1
- 若
- 重复步骤 2-3，直到
left > right（未找到）
代码实现
查找精确值
#include <bits/stdc++.h>
using namespace std;
// 查找精确值，找到返回索引，未找到返回 -1
int binarySearch(vector<int>& arr, int target) {
int left = 0, right = arr.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() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
cout << binarySearch(arr, 7) << endl; // 输出: 3
cout << binarySearch(arr, 6) << endl; // 输出: -1
return 0;
}查找左边界（第一个 target 的位置）
#include <bits/stdc++.h>
using namespace std;
// 查找左边界：第一个 >= target 的元素索引
int lowerBound(vector<int>& arr, int target) {
int left = 0, right = arr.size(); // 注意：right = n（不取等）
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid; // 继续向左收缩
}
}
return left; // 可能等于 n（未找到）
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
cout << lowerBound(arr, 6) << endl; // 输出: 3 (arr[3] = 7)
cout << lowerBound(arr, 7) << endl; // 输出: 3 (arr[3] = 7)
cout << lowerBound(arr, 16) << endl; // 输出: 8 (未找到，等于 n)
return 0;
}查找右边界（最后一个 target 的位置）
#include <bits/stdc++.h>
using namespace std;
// 查找右边界：最后一个 <= target 的元素索引
int upperBound(vector<int>& arr, int target) {
int left = 0, right = arr.size(); // 注意：right = n
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) {
left = mid + 1; // 继续向右收缩
} else {
right = mid;
}
}
return left - 1; // 可能等于 -1（未找到）
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
cout << upperBound(arr, 6) << endl; // 输出: 2 (arr[2] = 5)
cout << upperBound(arr, 7) << endl; // 输出: 3 (arr[3] = 7)
cout << upperBound(arr, 0) << endl; // 输出: -1 (未找到)
return 0;
}通用模板
#include <bits/stdc++.h>
using namespace std;
// 二分查找通用模板
int binarySearch(vector<int>& arr, int target) {
int left = 0, right = arr.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 lowerBound(vector<int>& arr, int target) {
int left = 0, right = arr.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) left = mid + 1;
else right = mid;
}
return left;
}
// 寻找右侧边界
int upperBound(vector<int>& arr, int target) {
int left = 0, right = arr.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) left = mid + 1;
else right = mid;
}
return left - 1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
cout << binarySearch(arr, 7) << endl; // 3
cout << lowerBound(arr, 6) << endl; // 3
cout << upperBound(arr, 6) << endl; // 2
return 0;
}典型应用场景
查找问题
- 在有序数组中查找特定元素
- 查找元素的插入位置
- 检查元素是否存在
求极值问题
- 寻找峰值元素：数组中某个元素大于其相邻元素
- 寻找旋转排序数组中的最小值2
- 在二维矩阵中搜索（矩阵每行每列均递增）
最优化问题
二分查找常用于求解最大化最小值或最小化最大值问题：
- 分配最大资源最小化时间（“搬运货物”、“渡河问题”）
- 最大化最小距离（“天线安置”、“最小注射速率”）
这类问题的解决思路是：先验证答案可行性，再二分搜索最优值。