On: Nearly all binary searches and mergesorts are brok...

[legosexmagic]

the right solution is to parametrize the search region as (offset, length) instead of (start, end). then the midpoint is just offset+length/2.

you can also remove that unpredictable branch in the loop if you want.

  whatever_t *bisect(whatever_t *offset, size_t length, whatever_t x) {
    while(size_t midpoint = length / 2) {
      bool side = x < offset[midpoint];
      midpoint &= side - 1;
      length >>= side;
      offset += midpoint;
      length -= midpoint;
    }
    return offset;
  }

[abecedarius → legosexmagic]

(offset, length) was how I coded it in the 90s, too, precisely because it made correctness clearer. "Nearly all" broken, hmph.