6.二分算法

二分

二分算法，也称为二分查找或折半查找，是一种在有序数组中查找特定元素的高效算法。以下是 C++ 中二分算法的相关内容：

算法原理

• 二分算法的基本思想是将有序数组分成两部分，然后将目标值与中间元素进行比较。如果目标值等于中间元素，则查找成功；如果目标值小于中间元素，则在数组的左半部分继续查找；如果目标值大于中间元素，则在数组的右半部分继续查找。重复这个过程，直到找到目标值或者确定目标值不存在于数组中。
• 通过 不断折半缩小搜索范围 的查找方式，时间复杂度为 O(log n)，需满足：
  1. 数据存储在 线性结构（如数组）
  2. 数据必须 有序（升序/降序）

代码实现

以下是一个使用 C++ 实现二分算法的示例代码：

#include <iostream>
#include <vector>

using namespace std;

// 二分查找函数
int binarySearch(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    while (left <= right) {
        // 避免溢出
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }

    // 目标值不存在于数组中
    return -1;
}

int main() {
    vector<int> nums = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int target = 7;

    int result = binarySearch(nums, target);

    if (result!= -1) {
        cout << "目标值 " << target << " 在数组中的索引为：" << result << endl;
    }
    else {
        cout << "目标值 " << target << " 不存在于数组中。" << endl;
    }

    return 0;
}

复杂度分析

• 时间复杂度：二分算法每次迭代都将搜索区间减半，因此时间复杂度为O(log n)，其中 是n数组的长度。这使得二分算法在处理大规模数据时非常高效。
• 空间复杂度：在上述代码中，除了输入的数组外，只使用了几个额外的变量，如left、right和mid，它们的数量不随输入规模增长，所以空间复杂度为O(1)。

应用场景

• 数据查找：在有序数组或有序列表中快速查找特定元素，如在电话号码簿、字典等数据结构中查找特定的记录。
• 求解方程：可以用于数值计算中求解方程的根。例如，对于一个单调递增或单调递减的函数，可以通过二分算法来逼近方程的解。
• 优化问题：在一些优化问题中，二分算法可以用于搜索最优解的范围。例如，在寻找最小化或最大化某个目标函数的参数时，可以利用二分算法来缩小搜索空间。

注意事项

• 二分算法要求数据必须是有序的。如果数据是无序的，需要先进行排序操作，这可能会增加额外的时间复杂度。
• 在实现二分算法时，需要注意边界条件的处理，以确保算法的正确性和稳定性。

在库中

C++在STL库中已经封装好了二分算法，我们只需要引入调用即可。

在 <algorithm> 头文件中提供以下关键函数：

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> nums = {1, 3, 5, 7, 9};
    
    // 查找是否存在
    bool exists = std::binary_search(nums.begin(), nums.end(), 5); // true
    
    // 查找插入位置
    auto lower = std::lower_bound(nums.begin(), nums.end(), 6); // 指向7
    int pos = lower - nums.begin(); // 插入位置索引为3
    
    // 统计元素出现次数
    auto upper = std::upper_bound(nums.begin(), nums.end(), 5);
    int count = upper - lower; // 1次
}