c++ 二分查找
二分法（Binary Search）是一种高效的查找算法，它在有序数组中查找一个元素，利用分治法的思想将查找空间逐步缩小一半。二分法的时间复杂度是 O(log n)，比起线性查找（O(n)）要高效得多。
基本思想
- 首先确定一个范围（通常是数组的左右边界）。
- 计算范围的中间位置。
- 如果中间位置的元素是目标元素，则返回该位置。
- 如果中间位置的元素大于目标元素，则将搜索范围缩小为中间元素左侧的部分。
- 如果中间位置的元素小于目标元素，则将搜索范围缩小为中间元素右侧的部分。
- 重复这个过程直到找到目标元素或者搜索区间为空。
代码实现
普通二分查找
#include <iostream>
#include <vector>
using namespace std;
int binarySearch(const vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
// int mid = left + (right - left) / 2; // 防止溢出
int mid = (left + right) >> 1;
if (arr[mid] == target) {
return mid; // 找到目标，返回索引
}
else if (arr[mid] < target) {
left = mid + 1; // 目标在右边
}
else {
right = mid - 1; // 目标在左边
}
}
return -1; // 如果没有找到目标，返回-1
}
int main() {
vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
int target = 7;
int index = binarySearch(arr, target);
if (-1 != index) {
cout << "元素 " << target << " 在数组中的位置是: " << index << endl;
} else {
cout << "元素 " << target << " 不在数组中。" << endl;
}
return 0;
}
查找插入位置
在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
// leetcode --- 35. 搜索插入位置
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
int ans = nums.size();
while (l <= r) {
int mid = (l + r) >> 1;
if (nums[mid] < target) {
l = mid + 1;
} else {
r = mid - 1;
ans = mid;
}
}
return ans;
}
应用
查找目标值的最左位置（查找重复元素的第一个位置）
当数组中有重复元素时，二分查找可以用来找到目标值的第一个出现位置。
问题描述：
给定一个升序排列的数组 arr 和一个目标值 target，请找出 target 在数组中首次出现的位置。
#include <iostream>
#include <vector>
using namespace std;
int binarySearchLeft(const vector<int>& arr, int target) {
int left = 0, right = arr.size();
while (left < right) {
int mid = left + (right - left) / 2;
// 如果当前值等于目标值，则向左侧继续查找
if (arr[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
// 检查 left 是否越界或值是否等于目标
if (left < arr.size() && arr[left] == target) {
return left;
}
return -1; // 未找到目标值
}
int main() {
vector<int> arr = {1, 2, 2, 2, 3, 4, 5};
int target = 2;
int index = binarySearchLeft(arr, target);
if (index != -1) {
cout << "目标值 " << target << " 首次出现在索引: " << index << endl;
} else {
cout << "目标值 " << target << " 不在数组中。" << endl;
}
return 0;
}
查找目标值的最右位置（查找重复元素的最后位置）
类似于查找最左位置，我们也可以通过二分查找来找到目标值的最后一个出现位置。
问题描述：
给定一个升序排列的数组 arr 和一个目标值 target，请找出 target 在数组中最后出现的位置。
#include <iostream>
#include <vector>
using namespace std;
int binarySearchRight(const 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;
}
}
// 检查 left 是否越界或值是否等于目标
if (left - 1 >= 0 && arr[left - 1] == target) {
return left - 1;
}
return -1; // 未找到目标值
}
int main() {
vector<int> arr = {1, 2, 2, 2, 3, 4, 5};
int target = 2;
int index = binarySearchRight(arr, target);
if (index != -1) {
cout << "目标值 " << target << " 最后出现在索引: " << index << endl;
} else {
cout << "目标值 " << target << " 不在数组中。" << endl;
}
return 0;
}
查找最小的满足条件的数
有时我们需要找到某个最小的满足特定条件的数，这通常使用二分查找来优化。例如，找出第一个大于等于某个值的元素。
问题描述：
给定一个升序数组 arr 和一个目标值 target，找到第一个大于等于 target 的元素。如果没有找到，则返回 -1。
#include <iostream>
#include <vector>
using namespace std;
int binarySearchLowerBound(const 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; // 搜索左边
}
}
// 检查是否越界
if (left < arr.size() && arr[left] >= target) {
return left;
}
return -1; // 没有找到满足条件的元素
}
int main() {
vector<int> arr = {1, 2, 4, 6, 8, 10};
int target = 5;
int index = binarySearchLowerBound(arr, target);
if (index != -1) {
cout << "第一个大于等于 " << target << " 的元素在索引: " << index << ", 值为 " << arr[index] << endl;
} else {
cout << "没有找到满足条件的元素。" << endl;
}
return 0;
}
求解旋转排序数组中的目标值
有时数组可能已经进行了旋转（比如，排序数组 arr = [4, 5, 6, 7, 0, 1, 2]），我们可以使用二分查找来找到目标值的位置。
问题描述：
给定一个旋转过的升序数组 arr 和一个目标值 target，请找出目标值在数组中的索引。如果不存在，返回 -1。
#include <iostream>
#include <vector>
using namespace std;
int searchRotatedArray(const 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; // 找到目标值
}
// 判断左边是否有序
if (arr[left] <= arr[mid]) {
if (arr[left] <= target && target < arr[mid]) {
right = mid - 1; // 目标在左边
} else {
left = mid + 1; // 目标在右边
}
} else {
// 右边有序
if (arr[mid] < target && target <= arr[right]) {
left = mid + 1; // 目标在右边
} else {
right = mid - 1; // 目标在左边
}
}
}
return -1; // 未找到目标值
}
int main() {
vector<int> arr = {6, 7, 9, 15, 19, 2, 3};
int target = 3;
int index = searchRotatedArray(arr, target);
if (index != -1) {
cout << "目标值 " << target << " 在数组中的索引是: " << index << endl;
} else {
cout << "目标值 " << target << " 不在数组中。" << endl;
}
return 0;
}
总结
-
时间复杂度：无论是普通的二分查找还是查找插入位置，时间复杂度都是 O(log n)，其中
n是数组的大小。 -
适用场景：二分查找仅适用于有序数组。如果数组是无序的，必须先对其进行排序才能使用二分法。