二分法（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是数组的大小。 -
适用场景：二分查找仅适用于有序数组。如果数组是无序的，必须先对其进行排序才能使用二分法。
