跳到主要内容

C++ 二分查找操作

什么是二分查找？​

二分查找（Binary Search）是一种高效的查找算法，它利用已排序序列的特性，通过将待查找的元素与序列中间位置的元素进行比较，每次可以排除一半的搜索范围，从而大大提高查找效率。二分查找的时间复杂度为 O(log n)，相比线性查找的 O(n)，在大数据量情况下效率提升显著。

前提条件

二分查找的关键前提是：序列必须已经排序。如果原始数据未排序，需要先进行排序操作才能应用二分查找。

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

C++的STL（Standard Template Library）在 <algorithm> 头文件中提供了四种主要的二分查找操作函数：

  1. binary_search: 检查元素是否存在
  2. lower_bound: 查找大于或等于某值的第一个元素位置
  3. upper_bound: 查找大于某值的第一个元素位置
  4. equal_range: 返回等于某值的元素范围

接下来，我们将详细介绍这些函数的使用方法和应用场景。

binary_search 函数​

基本语法​

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

binary_search 函数检查已排序范围 [first, last) 中是否包含等于 value 的元素。如果存在，返回 true，否则返回 false。

简单示例​

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

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50, 60, 70};
    
    // 检查值是否存在
    bool exists = std::binary_search(v.begin(), v.end(), 30);
    std::cout << "30 " << (exists ? "exists" : "does not exist") << " in the vector" << std::endl;
    
    // 检查不存在的值
    exists = std::binary_search(v.begin(), v.end(), 25);
    std::cout << "25 " << (exists ? "exists" : "does not exist") << " in the vector" << std::endl;
    
    return 0;
}

输出：

30 exists in the vector
25 does not exist in the vector

lower_bound 函数​

基本语法​

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

lower_bound 函数返回指向范围内第一个不小于（大于或等于）value 的元素的迭代器。如果所有元素都小于 value，则返回 last。

示例代码​

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

int main() {
    std::vector<int> v = {10, 20, 30, 30, 30, 40, 50};
    
    // 查找第一个大于或等于30的元素
    auto it = std::lower_bound(v.begin(), v.end(), 30);
    int position = it - v.begin();
    std::cout << "First element >= 30 is at position: " << position 
              << " with value: " << *it << std::endl;
    
    // 查找第一个大于或等于35的元素
    it = std::lower_bound(v.begin(), v.end(), 35);
    position = it - v.begin();
    std::cout << "First element >= 35 is at position: " << position 
              << " with value: " << *it << std::endl;
    
    return 0;
}

输出：

First element >= 30 is at position: 2 with value: 30
First element >= 35 is at position: 5 with value: 40

upper_bound 函数​

基本语法​

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

upper_bound 函数返回指向范围内第一个大于 value 的元素的迭代器。如果所有元素都不大于 value，则返回 last。

示例代码​

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

int main() {
    std::vector<int> v = {10, 20, 30, 30, 30, 40, 50};
    
    // 查找第一个大于30的元素
    auto it = std::upper_bound(v.begin(), v.end(), 30);
    int position = it - v.begin();
    std::cout << "First element > 30 is at position: " << position 
              << " with value: " << *it << std::endl;
    
    // 查找第一个大于35的元素
    it = std::upper_bound(v.begin(), v.end(), 35);
    position = it - v.begin();
    std::cout << "First element > 35 is at position: " << position 
              << " with value: " << *it << std::endl;
    
    return 0;
}

输出：

First element > 30 is at position: 5 with value: 40
First element > 35 is at position: 5 with value: 40

equal_range 函数​

基本语法​

cpp
pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value);
pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

equal_range 函数返回一个迭代器对（pair），其中第一个迭代器等价于 lower_bound，第二个迭代器等价于 upper_bound。这个函数实际上同时返回了一个元素的等值范围。

示例代码​

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

int main() {
    std::vector<int> v = {10, 20, 30, 30, 30, 40, 50};
    
    // 查找所有等于30的元素范围
    auto range = std::equal_range(v.begin(), v.end(), 30);
    int first_pos = range.first - v.begin();
    int last_pos = range.second - v.begin();
    int count = last_pos - first_pos;
    
    std::cout << "Elements equal to 30 start at position: " << first_pos << std::endl;
    std::cout << "Elements equal to 30 end at position: " << last_pos << std::endl;
    std::cout << "Number of elements equal to 30: " << count << std::endl;
    
    return 0;
}

输出：

Elements equal to 30 start at position: 2
Elements equal to 30 end at position: 5
Number of elements equal to 30: 3

二分查找算法的工作原理​

二分查找的基本原理可以用以下步骤描述：

  1. 确定查找范围的中间位置
  2. 将待查找的值与中间位置的元素比较
  3. 如果相等，则找到目标
  4. 如果待查找值小于中间元素，则在左半部分继续查找
  5. 如果待查找值大于中间元素，则在右半部分继续查找
  6. 重复以上步骤，直到找到目标或确定目标不存在

下面是一个简单的二分查找的图示：

实际应用场景​

场景一：字典查找​

字典通常是按字母顺序排列的，当我们查找一个单词时，实际上在使用二分查找的思想。

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

int main() {
    std::vector<std::string> dictionary = {
        "apple", "banana", "cherry", "date", "elderberry", 
        "fig", "grape", "honeydew", "kiwi", "lemon"
    };
    
    // 确保字典已排序
    std::sort(dictionary.begin(), dictionary.end());
    
    // 查找单词
    std::string target = "grape";
    if (std::binary_search(dictionary.begin(), dictionary.end(), target)) {
        std::cout << target << " 在字典中被找到!" << std::endl;
    } else {
        std::cout << target << " 不在字典中!" << std::endl;
    }
    
    return 0;
}

输出：

grape 在字典中被找到!

场景二：查找学生成绩范围​

假设我们有一个已排序的学生成绩列表，需要查找分数在某个范围内的学生数量：

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

int main() {
    // 已排序的学生成绩
    std::vector<int> scores = {60, 65, 70, 75, 80, 80, 85, 85, 85, 90, 95};
    
    // 查找成绩在80-90之间的学生数量
    auto lower = std::lower_bound(scores.begin(), scores.end(), 80);
    auto upper = std::upper_bound(scores.begin(), scores.end(), 90);
    
    int count = upper - lower;
    std::cout << "成绩在80到90之间（含）的学生数量: " << count << std::endl;
    
    // 查找成绩等于85的学生数量
    auto range = std::equal_range(scores.begin(), scores.end(), 85);
    count = range.second - range.first;
    std::cout << "成绩等于85的学生数量: " << count << std::endl;
    
    return 0;
}

输出：

成绩在80到90之间（含）的学生数量: 7
成绩等于85的学生数量: 3

场景三：自定义比较函数​

有时我们需要使用自定义的比较逻辑，STL的二分查找函数允许我们传入自定义的比较函数：

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

struct Student {
    std::string name;
    int score;
    
    // 构造函数
    Student(std::string n, int s) : name(n), score(s) {}
    
    // 用于排序的比较运算符
    bool operator<(const Student& other) const {
        return score < other.score; // 按分数升序排序
    }
};

// 自定义比较函数，只比较分数
bool compareByScore(const Student& s, int score) {
    return s.score < score;
}

int main() {
    std::vector<Student> students = {
        {"Alice", 85},
        {"Bob", 72},
        {"Charlie", 90},
        {"David", 78},
        {"Eve", 95}
    };
    
    // 按成绩排序
    std::sort(students.begin(), students.end());
    
    // 查找分数大于等于80的第一个学生
    auto it = std::lower_bound(students.begin(), students.end(), 80, 
                              [](const Student& s, int score) { return s.score < score; });
    
    if (it != students.end()) {
        std::cout << "第一个分数大于等于80的学生是: " << it->name 
                  << "，分数: " << it->score << std::endl;
    }
    
    return 0;
}

输出：

第一个分数大于等于80的学生是: Alice，分数: 85

总结​

二分查找是一种强大且高效的算法，特别适合在已排序数据中进行快速查询。C++ STL提供的四个二分查找函数各有特点：

  • binary_search: 检查元素是否存在
  • lower_bound: 查找第一个大于等于目标值的元素
  • upper_bound: 查找第一个大于目标值的元素
  • equal_range: 同时获取等值元素的开始和结束位置

记住，使用这些函数的前提是容器中的元素必须已经按照相同的比较标准排序。掌握这些二分查找算法可以大大提高你在处理已排序数据时的效率。

练习​

  1. 编写一个程序，使用二分查找在一个已排序的数组中查找一个数，如果找到则输出其位置，否则输出最适合插入该数的位置。

  2. 实现一个函数，用二分查找找出一个已排序数组中某个值出现的次数。

  3. 使用二分查找解决以下问题：在一个按升序排列的数组中，数组中的元素都是唯一的，请找出数组中任意一个峰值（比左右相邻元素大的元素）。

进阶资源​

  • 《C++ STL标准库开发指南》
  • C++ Reference - Binary search algorithms
  • LeetCode上有关二分查找的练习题目，如"搜索插入位置"、"在排序数组中查找元素的第一个和最后一个位置"等。