C++ 二分查找操作

二分查找（Binary Search）是计算机科学中一种高效的查找算法，适用于已排序的序列。C++标准模板库（STL）提供了多种二分查找算法，包括std::lower_bound、std::upper_bound、std::equal_range和std::binary_search。这些算法的时间复杂度为$O(\log n)$，适用于大规模数据查找。

算法原理

二分查找通过不断将搜索范围减半来快速定位目标元素。其基本步骤如下： 1. 确定当前搜索范围的中间元素。 2. 如果中间元素等于目标值，则查找成功。 3. 如果目标值小于中间元素，则在左半部分继续查找。 4. 如果目标值大于中间元素，则在右半部分继续查找。 5. 重复上述步骤，直到找到目标值或搜索范围为空。

graph TD A[开始] --> B{搜索范围是否为空?} B -->|是| C[查找失败] B -->|否| D[计算中间索引] D --> E{中间元素 == 目标值?} E -->|是| F[查找成功] E -->|否| G{目标值 < 中间元素?} G -->|是| H[在左半部分继续查找] G -->|否| I[在右半部分继续查找] H --> B I --> B

C++ STL中的二分查找算法

C++ STL提供了以下二分查找相关函数，均定义在<algorithm>头文件中：

std::binary_search

检查目标值是否存在于已排序的范围内。

语法

bool binary_search(ForwardIt first, ForwardIt last, const T& value);
bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp);

示例

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 3, 5, 7, 9};
    
    bool found = std::binary_search(v.begin(), v.end(), 5);
    std::cout << "5 exists: " << std::boolalpha << found << '\n';  // 输出: 5 exists: true
    
    found = std::binary_search(v.begin(), v.end(), 4);
    std::cout << "4 exists: " << found << '\n';  // 输出: 4 exists: false
}

std::lower_bound

返回第一个不小于目标值的元素的迭代器。

语法

ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value);
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp);

示例

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 4, 4, 5, 6};
    
    auto it = std::lower_bound(v.begin(), v.end(), 4);
    std::cout << "First element not less than 4 is at index " 
              << (it - v.begin()) << '\n';  // 输出: First element not less than 4 is at index 2
    
    it = std::lower_bound(v.begin(), v.end(), 3);
    std::cout << "First element not less than 3 is at index "
              << (it - v.begin()) << '\n';  // 输出: First element not less than 3 is at index 2
}

std::upper_bound

返回第一个大于目标值的元素的迭代器。

语法

ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value);
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp);

示例

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 4, 4, 5, 6};
    
    auto it = std::upper_bound(v.begin(), v.end(), 4);
    std::cout << "First element greater than 4 is at index "
              << (it - v.begin()) << '\n';  // 输出: First element greater than 4 is at index 4
}

std::equal_range

返回一个范围，包含所有等于目标值的元素。

语法

std::pair<ForwardIt, ForwardIt> equal_range(ForwardIt first, ForwardIt last, const T& value);
std::pair<ForwardIt, ForwardIt> equal_range(ForwardIt first, ForwardIt last, const T& value, Compare comp);

示例

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 4, 4, 5, 6};
    
    auto range = std::equal_range(v.begin(), v.end(), 4);
    std::cout << "Range of 4: [" << (range.first - v.begin()) 
              << ", " << (range.second - v.begin()) << ")\n";  // 输出: Range of 4: [2, 4)
}

性能比较

下表比较了不同查找方法的时间复杂度：

算法	时间复杂度	适用条件
线性查找	$O(n)$	无序序列
二分查找	$O(\log n)$	已排序序列

实际应用案例

案例1：游戏分数排行榜

在游戏中，玩家分数按降序排列，需要快速查找某个玩家的排名。

#include <algorithm>
#include <vector>
#include <iostream>
#include <functional>

int main() {
    std::vector<int> scores = {100, 90, 80, 70, 60, 50};
    
    // 使用greater<int>进行降序查找
    auto it = std::lower_bound(scores.begin(), scores.end(), 75, std::greater<int>());
    std::cout << "Score 75 would rank at position " 
              << (it - scores.begin() + 1) << '\n';  // 输出: Score 75 would rank at position 4
}

案例2：字典查询

在字典应用中快速查找单词是否存在。

#include <algorithm>
#include <vector>
#include <string>
#include <iostream>

int main() {
    std::vector<std::string> dictionary = {"apple", "banana", "cherry", "date", "fig"};
    
    bool found = std::binary_search(dictionary.begin(), dictionary.end(), "cherry");
    std::cout << "Word 'cherry' exists: " << std::boolalpha << found << '\n';  // 输出: Word 'cherry' exists: true
}

常见问题

Q1: 为什么我的二分查找结果不正确？

A: 最常见的原因是序列没有正确排序。二分查找要求输入范围必须是已排序的，否则结果不可预测。

Q2: 如何自定义比较函数？

A: 可以传递一个比较函数作为第四个参数。例如，对于降序排列的序列：

bool found = std::binary_search(v.begin(), v.end(), 5, std::greater<int>());

Q3: 什么时候使用equal_range而不是lower_bound/upper_bound？

A: 当需要同时获取等于目标值的元素的开始和结束位置时，使用equal_range更高效，它只需要一次二分查找而不是两次。

总结

C++ STL提供了强大的二分查找工具：

• binary_search - 检查元素是否存在
• lower_bound - 查找第一个不小于目标值的位置
• upper_bound - 查找第一个大于目标值的位置
• equal_range - 同时获取等于目标值的范围

这些算法是处理已排序数据时的首选工具，能显著提高查找效率。