C++ 的 二分查找

等级 5295 次按键

在已排序的 vector 上,binary_search 判断某个值是否存在,lower_bound 查找第一个不小于给定值的元素。两者都是 O(log n)。

C++ 代码

// 二分查找要求数据已排序
1vector<int> nums = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
2
// boolalpha 使 bool 显示为 true/false 而不是 1/0
3cout << boolalpha;
// 7 在 vector 中:输出 true
4cout << binary_search(nums.begin(), nums.end(), 7) << endl;
// 8 不在其中:输出 false
5cout << binary_search(nums.begin(), nums.end(), 8) << endl;
6
// 指向第一个 >= 10 的元素的迭代器
7auto it = lower_bound(nums.begin(), nums.end(), 10);
// 输出 11(若不存在这样的元素则为 end(),不能解引用)
8cout << "Lower bound of 10: " << *it << endl;

运行结果

true
false
Lower bound of 10: 11
用这段代码练习打字

可以用这段代码练习打字。成绩不会计入排行榜。

这段代码中的符号

这段 C++ 代码中需要输入的符号及其出现次数。

  • <× 17
  • ,× 15
  • (× 9
  • )× 9
  • ;× 6
  • .× 6
  • _× 3
  • "× 2
  • =× 2
  • :× 1

C++ 等级 5 的更多代码示例

← 返回 C++ 打字练习