C++ 二分法

二分法（Binary Search）是一种常用的查找算法，它通过将已排序的元素划分为两部分，然后通过比较目标值与划分点的大小关系，将查找范围缩小一半，从而快速地找到目标值。二分法的时间复杂度为O(logN)，很适合用于查找大规模数据中的目标值。在本篇博文中，我将介绍二分法的基本原理、C++代码实现以及一些实际应用，希望能够帮助大家更好地理解和应用这个算法。

目录：
1. 二分法的基本原理
2. C++代码实现
3. 二分法的应用实例
4. 总结

📚 1. 二分法的基本原理

二分法的基本原理可以概括为以下几个步骤：
1) 将已排序的数组或列表的首位索引分别记为low和high。
2) 取中间位置mid的索引，并取出对应的元素midValue。
3) 将目标值与midValue进行比较：
   - 如果目标值等于midValue，查找成功，返回mid。
   - 如果目标值小于midValue，说明目标值可能在左侧，将high更新为mid - 1，然后重复步骤2。
   - 如果目标值大于midValue，说明目标值可能在右侧，将low更新为mid + 1，然后重复步骤2。
4) 当low大于high时，查找失败，返回-1。

🖥️ 2. C++代码实现

下面是用C++语言实现二分法的代码示例：

#include <iostream>
#include <vector>using namespace std;int binarySearch(vector<int>& nums, int target) {int low = 0;int high = nums.size() - 1;while (low <= high) {int mid = low + (high - low) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {low = mid + 1;} else {high = mid - 1;}}return -1;
}int main() {vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};int target = 6;int index = binarySearch(nums, target);if (index != -1) {cout << "目标值在数组中的索引为：" << index << endl;} else {cout << "目标值不存在于数组中。" << endl;}return 0;
}

以上代码首先定义了一个名为binarySearch的函数，接受一个已排序的数组nums和目标值target作为参数，返回目标值在数组中的索引。函数内部使用了一个while循环来进行二分查找，通过不断更新low和high来缩小查找范围，直到找到目标值或者查找失败。

在main函数中，我们定义了一个测试用例nums和目标值target，并调用了binarySearch函数进行查找。结果会输出目标值在数组中的索引或者提示目标值不存在于数组中。

💡 3. 二分法的应用实例

二分法广泛应用于各种数据查找和优化问题中。下面是几个常见的应用实例：

- 查找数组中的目标元素：二分法可以高效地在已排序的数组中查找目标元素，时间复杂度为O(logN)。
- 旋转数组的查找：将已排序的数组按照某个索引旋转后，仍然可以使用二分法来查找目标元素。
- 查找数组中的峰值元素：峰值元素指的是大于其相邻元素的元素，二分法可以用来找到数组中的一个峰值元素。
- 查找有序矩阵中的目标元素：将有序矩阵视为一个已排序的二维数组，可以使用二分法在其中查找目标元素。

🔍 4. 总结

二分法是一种高效的查找算法，通过将已排序的元素划分为两部分，能够快速地定位目标元素。本篇博文介绍了二分法的基本原理、C++代码实现以及一些实际应用实例。希望对大家了解和应用二分法有所帮助。

如果对二分法还有疑问或者想了解更多相关内容，欢迎留言讨论！🎉