C++ 中二分查找库函数

函数简介#

C++ 标准库中提供了三个和二分查找相关的函数，都定义在头文件中，非常实用而且高效，下面是它们的功能和使用方法：

⸻

✅ 1. binary_search#

 判断某个元素是否存在于有序数组中

#include

bool found = binary_search(nums.begin(), nums.end(), target);

1
•  返回值：true 表示找到了 target，否则为 false。
2
•  时间复杂度：O(log n)

⸻

✅ 2. lower_bound#

 查找第一个大于等于 target 的元素的位置（返回迭代器）

auto it = lower_bound(nums.begin(), nums.end(), target);

int index = it - nums.begin(); // 获取下标

1
•  如果 target 存在，返回它的第一个出现位置；
2
•  如果不存在，返回第一个大于 target 的元素位置；
3
•  若返回 nums.end()，说明没有比 target 大或等于它的元素。

⸻

✅ 3. upper_bound#

 查找第一个大于 target 的元素的位置（返回迭代器）

auto it = upper_bound(nums.begin(), nums.end(), target);

int index = it - nums.begin(); // 获取下标

1
•  如果 target 存在多次，upper_bound 返回的是最后一个的下一个位置；
2
•  若返回 nums.end()，说明所有元素都 ≤ target。

⸻

 三者比较总结：#

函数名返回含义用法时间复杂度

binary_search 是否存在 target binary_search(v.begin(), v.end(), x) O(log n)

lower_bound 第一个 ≥ target 的位置 lower_bound(v.begin(), v.end(), x) O(log n)

upper_bound 第一个 > target 的位置 upper_bound(v.begin(), v.end(), x) O(log n)

⸻

離举个例子：

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
using namespace std;
5

6
int main() {
7
    vector<int> nums = {1, 2, 4, 4, 5, 6};
8
    int target = 4;
9

10
    cout << binary_search(nums.begin(), nums.end(), target) << endl; // 1 (true)
11
    cout << lower_bound(nums.begin(), nums.end(), target) - nums.begin() << endl; // 2
12
    cout << upper_bound(nums.begin(), nums.end(), target) - nums.begin() << endl; // 4
13

14
    return 0;
15
}

适用场景#

里示例 1：插入一个数使数组仍然有序#

1
vector<int> nums = {1, 3, 5, 7};
2
int target = 4;
3

4
// 插入 target 保持升序
5
auto it = lower_bound(nums.begin(), nums.end(), target);
6
nums.insert(it, target);  // 插入到合适位置
7

8
// 结果：nums = {1, 3, 4, 5, 7}
9
###  示例 2：查找数组中第一个 ≥ target 的元素

vector nums = {1, 3, 5, 7, 9}; int target = 6;

auto it = lower_bound(nums.begin(), nums.end(), target);

if (it != nums.end()) { cout << “第一个 ≥ ” << target << ” 的元素是 ” << *it << endl; } else { cout << “所有元素都小于 ” << target << endl; }

 示例 3：查找数组中第一个 > target 的元素#

1
vector<int> nums = {1, 3, 5, 7, 9};
2
int target = 5;
3

4
auto it = upper_bound(nums.begin(), nums.end(), target);
5

6
if (it != nums.end()) {
7
    cout << "第一个 > " << target << " 的元素是 " << *it << endl;
8
}
9
###  示例 4：查找元素出现的次数（重复元素）

vector nums = {1, 3, 3, 3, 5, 7}; int target = 3;

// 出现次数 = upper_bound - lower_bound int count = upper_bound(nums.begin(), nums.end(), target) - lower_bound(nums.begin(), nums.end(), target);

cout << “数字 ” << target << ” 出现了 ” << count << ” 次” << endl;

 示例 5：查找离 target 最近的数#

1
vector<int> nums = {1, 3, 6, 8, 10};
2
int target = 5;
3

4
auto it = lower_bound(nums.begin(), nums.end(), target);
5
int closest;
6

7
if (it == nums.begin()) {
8
    closest = *it;
9
} else if (it == nums.end()) {
10
    closest = *(--it);
11
} else {
12
    int a = *it;
13
    int b = *(--it);
14
    closest = (abs(a - target) < abs(b - target)) ? a : b;
15
}
16

17
cout << "离 " << target << " 最近的数是 " << closest << endl;

例题#

https://leetcode.cn/problems/maximum-count-of-positive-integer-and-negative-integer/

给你一个按非递减顺序排列的数组 nums ，返回正整数数目和负整数数目中的最大值。

换句话讲，如果 nums 中正整数的数目是 pos ，而负整数的数目是 neg ，返回 pos 和 neg二者中的最大值。

注意：0 既不是正整数也不是负整数。

示例 1：

输入：nums = [-2,-1,-1,1,2,3]

输出：3

解释：共有 3 个正整数和 3 个负整数。计数得到的最大值是 3 。

示例 2：

输入：nums = [-3,-2,-1,0,0,1,2]

输出：3

解释：共有 2 个正整数和 3 个负整数。计数得到的最大值是 3 。

示例 3：

输入：nums = [5,20,66,1314]

输出：4

解释：共有 4 个正整数和 0 个负整数。计数得到的最大值是 4 。

提示：

1 <= nums.length <= 2000

-2000 <= nums[i] <= 2000

nums 按非递减顺序排列。

进阶：你可以设计并实现时间复杂度为 O(log(n)) 的算法解决此问题吗？

1
#include <vector>
2
#include <algorithm>
3

4
using namespace std;
5

6
class Solution {
7
public:
8
    int maximumCount(vector<int>& nums) {
9
        // 统计负数：最后一个 <0 的位置 +1
10
        int neg = upper_bound(nums.begin(), nums.end(), -1) - nums.begin();
11

12
        // 统计正数：end - 第一个 >0 的位置
13
        int pos = nums.end() - lower_bound(nums.begin(), nums.end(), 1);
14

15
        return max(neg, pos);
16
    }
17
};

原文发布于 CSDN：C++ 中二分查找库函数