ucw/doc/binsearch.txt

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