Yet another binary search

Question

Code review my binary search! It isn't supposed to be superfast or anything. It's optimized for clarity and only sorts arrays of pointers. Also in the same style is my quicksort code review question: Yet another quicksort.

/*
  used as the base case of bsearch.
*/
static void const* misc_bsearch_linear(void const** A, void const** Z, void const* K, bool (*cmp)(void const*, void const*))
{
  /*
    burn forward while *A < K. if there is anything left, it will have
    to be that *A >= K.
  */
  while ((A < Z) && cmp(*A, K)) A++;

  /*
    if there is nothing left, we're done.
  */
  if (!(A < Z)) return NULL;

  /*
    now we know *A >= K.
  */
  {
    if (cmp(K, *A)) {
      /* when K < *A */
      /* this means *A > K, so no dice */
      return NULL;
    } else {
      /* when K >= *A */
      /* this means *A == K, so return it */
      return *A;
    }
  }
}

static void const* misc_bsearch_internal(void const** A, void const** Z, void const* K, bool (*cmp)(void const*, void const*))
{
  /*
    must stop loop when there are 3 or fewer elements, otherwise it
    could go on forever in the bottom case.
  */
  while ((Z - A) > 3) {
    void const** M = (A + ((Z - A) >> 1));

    if (cmp(*M, K)) {
      /* when *M < K */
      A = M + 1;
    } else {
      /* when *M >= K */
      Z = M + 1;
    }
  }

  /*
    we're down to at most 3 elements, to downgrade to linear search to
    finish up.
  */
  return misc_bsearch_linear(A, Z, K, cmp);
}

/*
  cmp should return true iff [arg1] < [arg2] (strictly).
*/
static INLINE void const* misc_bsearch(void const** A, uintptr_t L, void const* K, bool (*cmp)(void const*, void const*))
{
  return misc_bsearch_internal(A, (A + L), K, cmp);
}

#define MISC_BSEARCH_VARIANT(s, t)                                   \
  static INLINE t* misc_bsearch_##s(t** A, uintptr_t L, t const* K, bool (*cmp)(t const*, t const*)) \
  {                                                                  \
    return ((t*)(misc_bsearch(((void const**)(A)), L, K, ((bool (*)(void const*, void const*))(cmp))))); \
  }

Answer 1

Clarity

1. Reformat to the presentation width. Rather than incur slider bars,...

   static void const* misc_bsearch_internal(void const** A, void const** Z, void const* K, bool (*cmp)(void const*, void const*))
   

... wrap code

    static void const* misc_bsearch_internal(void const** A, void const** Z,
        void const* K, bool (*cmp)(void const*, void const*))

2. One letter argument names convey little,. Use more expressive names

   // static void const* misc_bsearch_linear(void const** A, 
   //    void const** Z, void const* K, bool (*cmp)(void const*, void const*))
   static void const* misc_bsearch_linear(void const** First, 
       void const** Last, void const* Key, bool (*cmp)(void const*, void const*))
   

3. const void * and void const * are the same, yet the one used by OP does not match the one used by the C standard. When looking for clarity, recommend following the standard's practice.

4. It is not stated if bool cmp() functions return true or false on match. For clarity, that should be detailed. OTOH. I eventually found it. For clarity, that should be detailed more obviously - at the top.

   // cmp should return true iff [arg1] < [arg2] (strictly).
   

5. Missing include.h files. I'd expect at least something for NULL and <stdint.h> the the optional types intptr_t / uintptr_t.

6. A sample usage (commented) of the entry function misc_bsearch() would be helpful. As it is, it is unclear how to use the function set.

---

Wider use

The compare functions used by the standard C library qsort() use a int cmp(....). As this code uses a bool cmp(....), the same function is not usable directly in the other. Consider changing this code change to use int cmp(....).

---

Limitation

"only sorts arrays of pointers." --> Op's code handles pointers to objects. Pointers to functions may be wider than void *.