Definitions
#define BIN_SEARCH_FIRST_GE_CMP(ary,N,x,ary_lt_x) ({ \
uint l = 0, r = (N); \
while (l < r) \
{ \
uint m = (l+r)/2; \
if (ary_lt_x(ary,m,x)) \
l = m+1; \
else \
r = m; \
} \
l; \
})
Find the first element not lower than x in the sorted array ary of N elements (non-decreasing order). 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. The time complexity is O(log(N)).
#define ARY_LT_NUM(ary,i,x) (ary)[i] < (x)
The default comparision macro for BIN_SEARCH_FIRST_GE_CMP().
#define BIN_SEARCH_FIRST_GE(ary,N,x) BIN_SEARCH_FIRST_GE_CMP(ary,N,x,ARY_LT_NUM)
Same as BIN_SEARCH_FIRST_GE_CMP(), but uses the default < operator for comparisions.
#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; })
Search the sorted array ary of N elements (non-decreasing) for the first occurence of x. Returns the index or -1 if no such element exists. Uses the < operator for comparisions.
Examples
You can find few examples of binary search usage. Although we define only few macros, they can be used for several different cases, for example to find lower elements in a (non-)decreasing array or even to find elements in a (non-)increasing array.
static int inc[10] = { 1, 4, 4, 5, 6, 10, 11, 20, 25, 50 };
static const char *str[5] = { "aaa", "abc", "bflmpsvz", "rep", "rep" };
static int dec[3] = { 5, 2, 1 };
// find the first equal element
printf("%d\n", BIN_SEARCH_EQ(inc, 10, 4)); // prints 1
printf("%d\n", BIN_SEARCH_EQ(inc, 10, 15)); // prints -1 (not found)
// find the first greater or equal element
printf("%d\n", BIN_SEARCH_GE(inc, 10, 9)); // prints 5
printf("%d\n", BIN_SEARCH_GE(inc, 10, 10)); // prints 5
printf("%d\n", BIN_SEARCH_GE(inc, 10, 4)); // prints 1
printf("%d\n", BIN_SEARCH_GE(inc, 10, 99)); // prints 10 (not found)
// find the last equal element (or -1 if does not exist)
#define CMP_LE(ary, i, x) ((ary[i]) <= (x))
int i = BIN_SEARCH_FIRST_GE_CMP(inc, 10, 4, CMP_LE);
printf("%d\n", (i && inc[i - 1] == 4) ? i - 1 : -1); // prints 2
// find the first greater element
printf("%d\n", BIN_SEARCH_FIRST_GE_CMP(inc, 10, 25, CMP_LE)); // prints 9
// find the last lower or equal element (or -1 if does not exist)
printf("%d\n", BIN_SEARCH_FIRST_GE_CMP(inc, 10, 25, CMP_LE) - 1); // prints 8
// find the last lower element (or -1 if does not exist)
printf("%d\n", BIN_SEARCH_FIRST_GE(inc, 10, 25) - 1); // prints 7
// find the first greater or equal string
#define CMP_STR(ary, i, x) (strcmp((ary[i]), (x)) < 0)
printf("%d\n", BIN_SEARCH_GE_CMP(str, 5, "bfl", CMP_STR)); // prints 2
// find the first lower or equal element in the non-increasing array
#define CMP_GT(ary, i, x) ((ary[i]) > (x))
printf("%d\n", BIN_SEARCH_FIRST_GE_CMP(dec, 3, 4, CMP_GT)); // prints 1