Posted on 2010-12-13 22:42
魔のkyo 阅读(359)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm
其实类似的东西我写过很多次了，从来不留模板，这次也在想要不要发上来存一下呢？
我觉得这种小东西应该时常写一下可以锻炼一下对算法的敏感，又一想不如发上来抹杀各位读者对算法的敏感，恩
//给定下确界(最大下界)，返回[b,e)上满足v<=*p的最小的p，如果不存在则返回的p不属于[b,e)，事实上是e
template<typename T>
const T* MLB(const T* const b, const T* const e, const T& v)
{
if(b>=e) return e;
const T* bb = b;
const T* ee = e;
while(ee-bb>2)
{
const T* mm = bb+(ee-bb)/2;
if(*mm<v)
{
bb = mm + 1;
}
else // v<=*p
{
ee = mm + 1;
}
}
for(const T* p = bb; p<ee;p++)
{
if(v<=*p)
{
return p;
}
}
return e;
}
//给定下(不确)界，返回[b,e)上满足v<*p的最小的p，如果不存在则返回的p不属于[b,e)，事实上是e
template<typename T>
const T* LB(const T* const b, const T* const e, const T& v)
{
if(b>=e) return e;
const T* bb = b;
const T* ee = e;
while(ee-bb>2)
{
const T* mm = bb+(ee-bb)/2;
if(*mm<=v)
{
bb = mm + 1;
}
else // v<*p
{
ee = mm + 1;
}
}
for(const T* p = bb; p<ee;p++)
{
if(v<*p)
{
return p;
}
}
return e;
}
//给定上确界(最小上界)，返回[b,e)上满足*p<=v的最大的p，如果不存在则返回的p不属于[b,e)，事实上是b-1
template<typename T>
const T* LUB(const T* const b, const T* const e, const T& v)
{
if(b>=e) return b-1;
const T* bb = b;
const T* ee = e;
while(ee-bb>2)
{
const T* m = bb+(ee-bb)/2;
if(*m<=v)
{
bb = m;
}
else // v<*p
{
ee = m;
}
}
for(const T* p = ee-1; p>=bb;p--)
{
if(*p<=v)
{
return p;
}
}
return b-1;
}
//给定上(不确)界，返回[b,e)上满足*p<v的最大的p，如果不存在则返回的p不属于[b,e)，事实上是b-1
template<typename T>
const T* UB(const T* const b, const T* const e, const T& v)
{
if(b>=e) return b-1;
const T* bb = b;
const T* ee = e;
while(ee-bb>2)
{
const T* m = bb+(ee-bb)/2;
if(*m<v)
{
bb = m;
}
else // v<=*p
{
ee = m;
}
}
for(const T* p = ee-1; p>=bb;p--)
{
if(*p<v)
{
return p;
}
}
return b-1;
}