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