|
|
typedef int REL(T)(const T*,const T*);//see Array_alg(3C++)template <class T> const T* bin_loc( const T& val, const T* b, const T* e ); template <class T> const T* bin_loc_r( int (*rel)(const T)*, const T)*), const T& val, const T* b, const T* e );
(1) For the plain version, T::operator< defines a total ordering relation on T and the array is sorted w.r.t. that relation.
(2) For the relational version, rel defines a total ordering relation on T and the array is sorted w.r.t. that relation.
These functions find the leftmost element in a sorted array greater than to val and return a pointer to it.
template <class T> const T* bin_loc( const T& val, const T* b, const T* e );
Uses T::operator< to find the element.
template <class T> const T* bin_loc_r( int (*rel)(const T)*, const T)*), const T& val, const T* b, const T* e );
Uses rel to find the element.
If N is the size of the array, then complexity is O(lgN). At most lgN tests of the ordering relation are done.
Because a Block (see Block(3C++)) can always be used wherever an array is called for, Array Algorithms can also be used with Blocks. In fact, these two components were actually designed to be used together.