bin_loc(C++)

Synopsis

   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
   );

Assumptions

(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.

Description

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.

Complexity

If N is the size of the array, then complexity is O(lgN). At most lgN tests of the ordering relation are done.

Notes

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.

References