众所周知STL常数起飞（
lower_bound与upper_bound尤其如此（
没事手写了个二分查找，功能用法返回值和STL一毛一样（只是不能传函数，如果是对自己的结构体排序要定义小于运算符QAQ）
然后测试了一下对 排序，STL耗时是我的5倍？？？
不是STL加了很多优化的吗
#include <cstdio>
namespace Template {
template<class T> inline T* lower_bound(T* First, T* Last, T val) {
T * L(First), * R(Last - 1);
while (L < R) {
T * mid(L + (R - L >> 1));
if (* mid < val) R = mid;
else L = mid + 1;
}
return !((* L) < val) ? L : Last;
}
template<class T> inline T* upper_bound(T* First, T* Last, T val) {
T * L(First), * R(Last - 1);
while (L < R) {
T * mid(L + (R - L >> 1));
if (val < * mid) R = mid;
else L = mid + 1;
}
return val < (*L) ? L : Last;
}
}
共 3 条回复
棒!
不是位置，是指向它的指针
我来给大家
科普科普lower_bound：找到第一个不小于改数的数的位置
upper_bound: 找到第一个大于该数的数的位置
但是没有不大于的函数，如果能不用不大于就不用不大于，要不大于才二分！！