ucw/binsearch.h

   1 /*
   2  *      UCW Library -- Generic Binary Search
   3  *
   4  *      (c) 2005 Martin Mares <mj@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 /***
  11  * [[defs]]
  12  * Definitions
  13  * -----------
  14  ***/
  15
  16 /**
  17  * Find the first element not lower than @x in the sorted array @ary of @N elements (non-decreasing order).
  18  * Returns the index of the found element or @N if no exists. Uses `ary_lt_x(ary,i,x)` to compare the @i'th element with @x.
  19  * The time complexity is `O(log(N))`.
  20  **/
  21 #define BIN_SEARCH_FIRST_GE_CMP(ary,N,x,ary_lt_x)  ({           \
  22   uns l = 0, r = (N);                                           \
  23   while (l < r)                                                 \
  24     {                                                           \
  25       uns m = (l+r)/2;                                          \
  26       if (ary_lt_x(ary,m,x))                                    \
  27         l = m+1;                                                \
  28       else                                                      \
  29         r = m;                                                  \
  30     }                                                           \
  31   l;                                                            \
  32 })
  33
  34 /**
  35  * The default comparision macro for @BIN_SEARCH_FIRST_GE_CMP().
  36  **/
  37 #define ARY_LT_NUM(ary,i,x) (ary)[i] < (x)
  38
  39 /**
  40  * Same as @BIN_SEARCH_FIRST_GE_CMP(), but uses the default `<` operator for comparisions.
  41  **/
  42 #define BIN_SEARCH_FIRST_GE(ary,N,x) BIN_SEARCH_FIRST_GE_CMP(ary,N,x,ARY_LT_NUM)
  43
  44 /**
  45  * Search the sorted array @ary of @N elements (non-decreasing) for the first occurence of @x.
  46  * Returns the index or -1 if no such element exists. Uses the `<` operator for comparisions.
  47  **/
  48 #define BIN_SEARCH_EQ(ary,N,x) ({ int i = BIN_SEARCH_FIRST_GE(ary,N,x); if (i >= (N) || (ary)[i] != (x)) i=-1; i; })