二分答案，二分搜索，封装
namespace binarySearch {
// 最后一个小于等于
template <typename T>
T* binarySearchLastSmall(T* l,T* r,int key) {
while(l+1<r) {
T* mid=l+(r-l)/2;
if(*mid<=key) l=mid;
else r=mid;
}
return l;
}
// 最后一个小于
template <typename T>
T* binarySearchLastSmallEx(T* l,T* r,int key) {
while(l+1<r) {
T* mid=l+(r-l)/2;
if(*mid<=key) l=mid;
else r=mid;
}
return l;
}
// 最后一个大于等于
template <typename T>
T* binarySearchLastBig(T* l,T* r,int key) {
while(l+1<r) {
T* mid=l+(r-l)/2;
if(*mid>=key) l=mid;
else r=mid;
}
return l;
}
// 最后一个大于
template <typename T>
T* binarySearchLastBigEx(T* l,T* r,T key) {
while(l+1<r) {
T* mid=l+(r-l)/2;
if(*mid>key) l=mid;
else r=mid;
}
return l;
}
// 自定义
template <typename T>
T binarySearchEverything(T l,T r,T key,bool (*comp)(T)) {
while(l+1<r) {
T mid=l+(r-l)/2;
if(comp(mid)) l=mid;
else r=mid;
}
return l;
}
};
using namespace binarySearch;
拿走拿走。