2 * UCW Library -- Generic Binary Search
4 * (c) 2005 Martin Mares <mj@ucw.cz>
6 * This software may be freely distributed and used according to the terms
7 * of the GNU Lesser General Public License.
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))`.
21 #define BIN_SEARCH_FIRST_GE_CMP(ary,N,x,ary_lt_x) ({ \
22 uint l = 0, r = (N); \
26 if (ary_lt_x(ary,m,x)) \
35 * The default comparision macro for @BIN_SEARCH_FIRST_GE_CMP().
37 #define ARY_LT_NUM(ary,i,x) (ary)[i] < (x)
40 * Same as @BIN_SEARCH_FIRST_GE_CMP(), but uses the default `<` operator for comparisions.
42 #define BIN_SEARCH_FIRST_GE(ary,N,x) BIN_SEARCH_FIRST_GE_CMP(ary,N,x,ARY_LT_NUM)
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.
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; })