在實(shí)現(xiàn)里面，使用了兩個可變類型，為了應(yīng)對在一堆結(jié)構(gòu)數(shù)組中按照一個成員來搜索。
template <class T1, class T2>
struct def_binary_search_compare
{
inline int operator()( const T1 & v1, const T2 & v2 ){
if( v1 == v2 )return 0;
if( v1 > v2 )return 1;
return -1;
}
};
template <class T1, class T2, typename cmpT = def_binary_search_compare<T1, T2> >
struct xbinary_search
{
static inline int search_insertpoint( const T1 * pTArray, int nArraySize, const T2 & v )
{
int insertpoint;
_search( pTArray, nArraySize, v, insertpoint );
return insertpoint;
}
static inline int search_value( const T1 * pTArray, int nArraySize, const T2 & v )
{
int insertpoint;
return _search( pTArray, nArraySize, v, insertpoint );
}
private:
static typename cmpT _cmp;
static inline int _search( const T1 * pTArray, int nArraySize, const T2 & v, int & insertpoint )
{
int s = 0, e = nArraySize, m, ret;
while( s < e )
{
m = (s+e)/2;
ret = _cmp( pTArray[m], v );
if( ret == 0 )
{
insertpoint = m;
return m;
}
if( ret > 0 )
e = m;
else
{
if( s == m )
break;
s = m+1;
}
}
insertpoint = e;
return -1;
}
};
template <class T1, class T2, typename cmpT>
typename cmpT xbinary_search<T1,T2,cmpT>::_cmp;很簡單的一個算法。相信都看得懂。