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/03cout << boolalpha;// 7 在 vector 中:输出 true4cout << binary_search(nums.begin(), nums.end(), 7) << endl;// 8 不在其中:输出 false5cout << 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