Range#bsearch

static VALUE
range_bsearch(VALUE range)
{
    VALUE beg, end, satisfied = Qnil;
    int smaller;

    /* Implementation notes:
     * Floats are handled by mapping them to 64 bits integers.
     * Apart from sign issues, floats and their 64 bits integer have the
     * same order, assuming they are represented as exponent followed
     * by the mantissa. This is true with or without implicit bit.
     *
     * Finding the average of two ints needs to be careful about
     * potential overflow (since float to long can use 64 bits)
     * as well as the fact that -1/2 can be 0 or -1 in C89.
     *
     * Note that -0.0 is mapped to the same int as 0.0 as we don't want
     * (-1...0.0).bsearch to yield -0.0.
     */

#define BSEARCH(conv) \
    do { \
        RETURN_ENUMERATOR(range, 0, 0); \
        if (EXCL(range)) high--; \
        org_high = high; \
        while (low < high) { \
            mid = ((high < 0) == (low < 0)) ? low + ((high - low) / 2) \
                : (low < -high) ? -((-1 - low - high)/2 + 1) : (low + high) / 2; \
            BSEARCH_CHECK(conv(mid)); \
            if (smaller) { \
                high = mid; \
            } \
            else { \
                low = mid + 1; \
            } \
        } \
        if (low == org_high) { \
            BSEARCH_CHECK(conv(low)); \
            if (!smaller) return Qnil; \
        } \
        return satisfied; \
    } while (0)


    beg = RANGE_BEG(range);
    end = RANGE_END(range);

    if (FIXNUM_P(beg) && FIXNUM_P(end)) {
        long low = FIX2LONG(beg);
        long high = FIX2LONG(end);
        long mid, org_high;
        BSEARCH(INT2FIX);
    }
#if SIZEOF_DOUBLE == 8 && defined(HAVE_INT64_T)
    else if (RB_FLOAT_TYPE_P(beg) || RB_FLOAT_TYPE_P(end)) {
        int64_t low  = double_as_int64(NIL_P(beg) ? -HUGE_VAL : RFLOAT_VALUE(rb_Float(beg)));
        int64_t high = double_as_int64(NIL_P(end) ?  HUGE_VAL : RFLOAT_VALUE(rb_Float(end)));
        int64_t mid, org_high;
        BSEARCH(int64_as_double_to_num);
    }
#endif
    else if (is_integer_p(beg) && is_integer_p(end)) {
        RETURN_ENUMERATOR(range, 0, 0);
        return bsearch_integer_range(beg, end, EXCL(range));
    }
    else if (is_integer_p(beg) && NIL_P(end)) {
        VALUE diff = LONG2FIX(1);
        RETURN_ENUMERATOR(range, 0, 0);
        while (1) {
            VALUE mid = rb_funcall(beg, '+', 1, diff);
            BSEARCH_CHECK(mid);
            if (smaller) {
                return bsearch_integer_range(beg, mid, 0);
            }
            diff = rb_funcall(diff, '*', 1, LONG2FIX(2));
        }
    }
    else if (NIL_P(beg) && is_integer_p(end)) {
        VALUE diff = LONG2FIX(-1);
        RETURN_ENUMERATOR(range, 0, 0);
        while (1) {
            VALUE mid = rb_funcall(end, '+', 1, diff);
            BSEARCH_CHECK(mid);
            if (!smaller) {
                return bsearch_integer_range(mid, end, 0);
            }
            diff = rb_funcall(diff, '*', 1, LONG2FIX(2));
        }
    }
    else {
        rb_raise(rb_eTypeError, "can't do binary search for %s", rb_obj_classname(beg));
    }
    return range;
}