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 #pragma once 11 12 /*** 13 * [[defs]] 14 * Definitions 15 * ----------- 16 ***/ 17 18 /** 19 * Find the first element not lower than \p x in the sorted array \p ary of \p N elements (non-decreasing order). 20 * Returns the index of the found element or \p N if no exists. Uses `ary_lt_x(ary,i,x)` to compare the i'th element with \p x. 21 * The time complexity is `O(log(N))`. 22 **/ 23 #define BIN_SEARCH_FIRST_GE_CMP(ary, N, ary_lt_x, x, ...) ({ \ 24 unsigned l = 0, r = (N); \ 25 while (l < r) \ 26 { \ 27 unsigned m = (l+r)/2; \ 28 if (ary_lt_x(ary, m, x, __VA_ARGS__)) \ 29 l = m+1; \ 30 else \ 31 r = m; \ 32 } \ 33 l; \ 34 }) 35 36 /** 37 * The default comparison macro for \ref BIN_SEARCH_FIRST_GE_CMP(). 38 **/ 39 #define ARY_LT_NUM(ary,i,x) (ary)[i] < (x) 40 41 /** 42 * Same as \ref BIN_SEARCH_FIRST_GE_CMP(), but uses the default `<` operator for comparisons. 43 **/ 44 #define BIN_SEARCH_FIRST_GE(ary,N,x) BIN_SEARCH_FIRST_GE_CMP(ary,N,ARY_LT_NUM,x) 45 46 /** 47 * Search the sorted array \p ary of \p N elements (non-decreasing) for the first occurrence of \p x. 48 * Returns the index or -1 if no such element exists. Uses the `<` operator for comparisons. 49 **/ 50 #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; }) 51