ucw/doc/binsearch.txt

   1 Binary search
   2 =============
   3
   4 * <<defs,Definitions>>
   5 * <<examples,Examples>>
   6
   7 !!ucw/binsearch.h
   8
   9 [[examples]]
  10 Examples
  11 --------
  12
  13 You can find few examples of binary search usage. Although we define only few macros, they can be used
  14 for several different cases, for example to find lower elements in a (non-)decreasing array or even to find
  15 elements in a (non-)increasing array.
  16
  17   static int inc[10] = { 1, 4, 4, 5, 6, 10, 11, 20, 25, 50 };
  18   static const char *str[5] = { "aaa", "abc", "bflmpsvz", "rep", "rep" };
  19   static int dec[3] = { 5, 2, 1 };
  20
  21   // find the first equal element
  22   printf("%d\n", BIN_SEARCH_EQ(inc, 10, 4));                            // prints 1
  23   printf("%d\n", BIN_SEARCH_EQ(inc, 10, 15));                           // prints -1 (not found)
  24
  25   // find the first greater or equal element
  26   printf("%d\n", BIN_SEARCH_GE(inc, 10, 9));                            // prints 5
  27   printf("%d\n", BIN_SEARCH_GE(inc, 10, 10));                           // prints 5
  28   printf("%d\n", BIN_SEARCH_GE(inc, 10, 4));                            // prints 1
  29   printf("%d\n", BIN_SEARCH_GE(inc, 10, 99));                           // prints 10 (not found)
  30
  31   // find the last equal element (or -1 if does not exist)
  32   #define CMP_LE(ary, i, x) ((ary[i]) <= (x))
  33   int i = BIN_SEARCH_FIRST_GE_CMP(inc, 10, 4, CMP_LE);
  34   printf("%d\n", (i && inc[i - 1] == 4) ? i - 1 : -1);                  // prints 2
  35
  36   // find the first greater element
  37   printf("%d\n", BIN_SEARCH_FIRST_GE_CMP(inc, 10, 25, CMP_LE));         // prints 9
  38
  39   // find the last lower or equal element (or -1 if does not exist)
  40   printf("%d\n", BIN_SEARCH_FIRST_GE_CMP(inc, 10, 25, CMP_LE) - 1);     // prints 8
  41
  42   // find the last lower element (or -1 if does not exist)
  43   printf("%d\n", BIN_SEARCH_FIRST_GE(inc, 10, 25) - 1);                 // prints 7
  44
  45   // find the first greater or equal string
  46   #define CMP_STR(ary, i, x) (strcmp((ary[i]), (x)) < 0)
  47   printf("%d\n", BIN_SEARCH_GE_CMP(str, 5, "bfl", CMP_STR));            // prints 2
  48
  49   // find the first lower or equal element in the non-increasing array
  50   #define CMP_GT(ary, i, x) ((ary[i]) > (x))
  51   printf("%d\n", BIN_SEARCH_FIRST_GE_CMP(dec, 3, 4, CMP_GT));           // prints 1