引言：
在计算机科学中，算法是解决问题的基石。今天，我们要介绍一种简单而强大的搜索算法——二分查找。它能够让我们以对数级的时间复杂度在有序数组中快速定位目标元素。
正文：
什么是二分查找算法？
二分查找是一种在有序数组中查找特定元素的算法。它通过将数组分成两半，并逐步缩小搜索范围，直到找到目标元素或确定元素不存在。
算法原理
二分查找的基本思想是：
- 取数组中间的元素与目标值比较。
- 如果中间元素等于目标值，则查找成功。
- 如果中间元素大于目标值，则在数组左半部分继续查找。
- 如果中间元素小于目标值，则在数组右半部分继续查找。
算法步骤
1. 初始化：设置两个指针，分别指向数组的起始和结束位置。
2. 循环条件：只要起始指针不大于结束指针，就继续循环。
3. 计算中间位置：找到中间位置，并与目标值进行比较。
4. 更新搜索范围：根据比较结果，更新搜索范围的起始或结束指针。
5. 循环结束：如果找到目标值，返回其位置；如果循环结束仍未找到，返回-1。
C++实现示例
```cppusing namespace std;int binarySearch(int arr[], int l, int r, int target) {while (l <= r) {int mid = l + (r - l) / 2;if (arr[mid] == target) return mid;if (arr[mid] > target) r = mid - 1;else l = mid + 1;}return -1;}int main() {int arr[] = {2, 3, 4, 10, 40};int target = 10;int result = binarySearch(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1, target);if (result != -1) {cout << "元素 " << target << " 的位置是：" << result << endl;} else {cout << "元素 " << target << " 在数组中不存在。" << endl;}return 0;}```
练手习题：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
参考代码：
class Solution {public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2if (nums[middle] > target) {right = middle - 1; // target 在左区间，所以[left, middle - 1]} else if (nums[middle] < target) {left = middle + 1; // target 在右区间，所以[middle + 1, right]} else { // nums[middle] == targetreturn middle; // 数组中找到目标值，直接返回下标}}// 未找到目标值return -1;}};
注意事项
- 确保数组是有序的。
- 时间复杂度为O(log n)，适用于大规模数据集。
- 当数组中有多个相同元素时，可能找到任意一个匹配元素。
结语
二分查找算法以其高效性在计算机科学中占据重要地位。无论是在软件开发、数据分析还是算法竞赛中，它都是一个值得掌握的工具。希望本文能帮助你更好地理解和应用二分查找算法。
结尾：
如果你对二分查找算法有更深的兴趣或疑问，欢迎在评论区留言讨论。让我们一起探索更多算法的奥秘！
