编辑“︁C++ 二分查找操作”︁

{{DISPLAYTITLE:C++二分查找操作}}

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

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

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

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

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

==== 语法 ====
<syntaxhighlight lang="cpp">
bool binary_search(ForwardIt first, ForwardIt last, const T& value);
bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp);
</syntaxhighlight>

==== 示例 ====
<syntaxhighlight lang="cpp">
#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
}
</syntaxhighlight>

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

==== 语法 ====
<syntaxhighlight lang="cpp">
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value);
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp);
</syntaxhighlight>

==== 示例 ====
<syntaxhighlight lang="cpp">
#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
}
</syntaxhighlight>

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

==== 语法 ====
<syntaxhighlight lang="cpp">
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value);
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp);
</syntaxhighlight>

==== 示例 ====
<syntaxhighlight lang="cpp">
#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
}
</syntaxhighlight>

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

==== 语法 ====
<syntaxhighlight lang="cpp">
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);
</syntaxhighlight>

==== 示例 ====
<syntaxhighlight lang="cpp">
#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)
}
</syntaxhighlight>

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

{| class="wikitable"
|-
! 算法 !! 时间复杂度 !! 适用条件
|-
| 线性查找 || <math>O(n)</math> || 无序序列
|-
| 二分查找 || <math>O(\log n)</math> || 已排序序列
|}

== 实际应用案例 ==
=== 案例1：游戏分数排行榜 ===
在游戏中，玩家分数按降序排列，需要快速查找某个玩家的排名。

<syntaxhighlight lang="cpp">
#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
}
</syntaxhighlight>

=== 案例2：字典查询 ===
在字典应用中快速查找单词是否存在。

<syntaxhighlight lang="cpp">
#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
}
</syntaxhighlight>

== 常见问题 ==
=== Q1: 为什么我的二分查找结果不正确？ ===
'''A:''' 最常见的原因是序列没有正确排序。二分查找要求输入范围必须是已排序的，否则结果不可预测。

=== Q2: 如何自定义比较函数？ ===
'''A:''' 可以传递一个比较函数作为第四个参数。例如，对于降序排列的序列：
<syntaxhighlight lang="cpp">
bool found = std::binary_search(v.begin(), v.end(), 5, std::greater<int>());
</syntaxhighlight>

=== Q3: 什么时候使用equal_range而不是lower_bound/upper_bound？ ===
'''A:''' 当需要同时获取等于目标值的元素的开始和结束位置时，使用<code>equal_range</code>更高效，它只需要一次二分查找而不是两次。

== 总结 ==
C++ STL提供了强大的二分查找工具：
* <code>binary_search</code> - 检查元素是否存在
* <code>lower_bound</code> - 查找第一个不小于目标值的位置
* <code>upper_bound</code> - 查找第一个大于目标值的位置
* <code>equal_range</code> - 同时获取等于目标值的范围

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

[[Category:编程语言]]
[[Category:C++]]
[[Category:C++stl 算法]]