Method: Range#bsearch

Defined in:

range.c

#bsearch {|obj| ... } ⇒ Object

Returns an element from self selected by a binary search.

See Binary Searching.

Yields:

• (obj)

# File 'range.c', line 790

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).
     *
     * The half-open interval (low, high] indicates where the target is located.
     * The loop continues until low and high are adjacent.
     *
     * -1/2 can be either 0 or -1 in C89. However, when low and high are not adjacent,
     * the rounding direction of mid = (low + high) / 2 does not affect the result of
     * the binary search.
     *
     * 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, excl) \
    do { \
        RETURN_ENUMERATOR(range, 0, 0); \
        if (!(excl)) high++; \
        low--; \
        while (low + 1 < high) { \
            mid = ((high < 0) == (low < 0)) ? low + ((high - low) / 2) \
                : (low + high) / 2; \
            BSEARCH_CHECK(conv(mid)); \
            if (smaller) { \
                high = mid; \
            } \
            else { \
                low = mid; \
            } \
        } \
        return satisfied; \
    } while (0)

#define BSEARCH_FIXNUM(beg, end, excl) \
    do { \
        long low = FIX2LONG(beg); \
        long high = FIX2LONG(end); \
        long mid; \
        BSEARCH(INT2FIX, (excl)); \
    } while (0)

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

    if (FIXNUM_P(beg) && FIXNUM_P(end)) {
        BSEARCH_FIXNUM(beg, end, EXCL(range));
    }
#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;
        BSEARCH(int64_as_double_to_num, EXCL(range));
    }
#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) {
                if (FIXNUM_P(beg) && FIXNUM_P(mid)) {
                    BSEARCH_FIXNUM(beg, mid, false);
                }
                else {
                    return bsearch_integer_range(beg, mid, false);
                }
            }
            diff = rb_funcall(diff, '*', 1, LONG2FIX(2));
            beg = mid;
        }
    }
    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) {
                if (FIXNUM_P(mid) && FIXNUM_P(end)) {
                    BSEARCH_FIXNUM(mid, end, false);
                }
                else {
                    return bsearch_integer_range(mid, end, false);
                }
            }
            diff = rb_funcall(diff, '*', 1, LONG2FIX(2));
            end = mid;
        }
    }
    else {
        rb_raise(rb_eTypeError, "can't do binary search for %s", rb_obj_classname(beg));
    }
    return range;
}