CRoaring uses 4-wise binary search, experiments in Go roaring

[lemire]

In C, this binary search function proved useful...

static void binarySearch4(const uint16_t *array, int32_t n, uint16_t target1,
                   uint16_t target2, uint16_t target3, uint16_t target4,
                   int32_t *index1, int32_t *index2, int32_t *index3,
                   int32_t *index4) {
  const uint16_t *base1 = array;
  const uint16_t *base2 = array;
  const uint16_t *base3 = array;
  const uint16_t *base4 = array;
  if (n == 0)
    return;
  while (n > 1) {
    int32_t half = n >> 1;
    base1 = (base1[half] < target1) ? &base1[half] : base1;
    base2 = (base2[half] < target2) ? &base2[half] : base2;
    base3 = (base3[half] < target3) ? &base3[half] : base3;
    base4 = (base4[half] < target4) ? &base4[half] : base4;
    n -= half;
  }
  *index1 = (*base1 < target1) + base1 - array;
  *index2 = (*base2 < target2) + base2 - array;
  *index3 = (*base3 < target3) + base3 - array;
  *index4 = (*base4 < target4) + base4 - array;
}

https://github.com/RoaringBitmap/CRoaring/blob/master/src/array_util.c#L695-L717