折半查找（Binary Search）
折半查找（也称二分查找）是一种在 有序数组 中查找目标值的高效算法。它的基本思想是：
- 每次取数组的中间元素，与目标值进行比较。
- 如果目标值小于中间元素，则查找范围缩小到左半部分；
- 如果目标值大于中间元素，则查找范围缩小到右半部分；
- 重复以上步骤，直到找到目标值或范围缩小为空。
时间复杂度：
- 最坏情况：
O(log n)（每次查找范围减少一半）。 - 最优情况：
O(1)（目标值一开始就在中间）。 - 平均情况：
O(log n)。 - 适用于大规模 有序数据，远比
O(n)的顺序查找高效。
1. 递归实现折半查找
思路
- 计算中间索引
mid = left + (right - left) / 2。 - 递归：
arr[mid] == target，找到目标值，返回索引。arr[mid] > target，递归搜索左半部分。arr[mid] < target，递归搜索右半部分。
代码
#include <iostream>
using namespace std;
int binarySearchRecursive(int arr[], int left, int right, int target) {
if (left > right) return -1; // 终止条件
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] > target) return binarySearchRecursive(arr, left, mid - 1, target);
else return binarySearchRecursive(arr, mid + 1, right, target);
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 7;
int result = binarySearchRecursive(arr, 0, n - 1, target);
if (result != -1)
cout << "找到目标值 " << target << "，索引为：" << result << endl;
else
cout << "目标值 " << target << " 不存在" << endl;
return 0;
}特点：
- 代码结构清晰，符合递归思想。
- 递归深度最多
log n，不会占用太多栈空间。
2. 迭代实现折半查找
思路
- 使用循环代替递归，避免函数调用的额外开销。
- 通过
left和right变量控制查找范围。 - 当
left <= right时继续查找，否则停止。
代码
#include <iostream>
using namespace std;
int binarySearchIterative(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] > target) right = mid - 1;
else left = mid + 1;
}
return -1; // 未找到
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 11;
int result = binarySearchIterative(arr, n, target);
if (result != -1)
cout << "找到目标值 " << target << "，索引为：" << result << endl;
else
cout << "目标值 " << target << " 不存在" << endl;
return 0;
}特点：
- 避免递归的函数调用开销，更适合大规模数据。
- 时间复杂度仍为
O(log n)，但空间复杂度降为O(1)（递归版本的栈消耗O(log n)）。
3. 变种折半查找
(1) 查找第一个出现的位置
适用于数组中有重复元素的情况，寻找最左侧匹配的索引。
代码
int binarySearchFirstOccurrence(int arr[], int n, int target) {
int left = 0, right = n - 1, result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] >= target) {
if (arr[mid] == target) result = mid;
right = mid - 1; // 继续向左搜索
} else {
left = mid + 1;
}
}
return result;
}例子
int arr[] = {1, 2, 2, 2, 3, 4, 5};
int result = binarySearchFirstOccurrence(arr, 7, 2);
cout << result; // 输出 1(2) 查找最后一个出现的位置
代码
int binarySearchLastOccurrence(int arr[], int n, int target) {
int left = 0, right = n - 1, result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) {
if (arr[mid] == target) result = mid;
left = mid + 1; // 继续向右搜索
} else {
right = mid - 1;
}
}
return result;
}例子
int arr[] = {1, 2, 2, 2, 3, 4, 5};
int result = binarySearchLastOccurrence(arr, 7, 2);
cout << result; // 输出 3(3) 查找第一个大于等于目标值的位置
int binarySearchLowerBound(int arr[], int n, int target) {
int left = 0, right = n - 1, result = n;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] >= target) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}例子
int arr[] = {1, 3, 5, 7, 9};
int result = binarySearchLowerBound(arr, 5, 6);
cout << result; // 输出 3（即索引 3 的元素 7）(4) 查找最后一个小于等于目标值的位置
int binarySearchUpperBound(int arr[], int n, int target) {
int left = 0, right = n - 1, result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}例子
int arr[] = {1, 3, 5, 7, 9};
int result = binarySearchUpperBound(arr, 5, 6);
cout << result; // 输出 2（即索引 2 的元素 5）总结
- 折半查找适用于有序数组，时间复杂度
O(log n)，远优于顺序查找O(n)。 - 迭代比递归更节省空间，推荐使用。
- 可以扩展为查找最左、最右、上下界等问题，实用性强。
折半查找是基础但极其高效的查找算法，熟练掌握后能优化多种搜索问题！
