method

bsearch_index

v2_4_6 - Show latest stable - 0 notes - Class: Array

1_8_6_287
1_8_7_72
1_8_7_330
1_9_1_378
1_9_2_180
1_9_3_125
1_9_3_392
2_1_10
2_2_9
2_4_6 (0)
2_5_5 (38)
2_6_3 (0)
What's this?

bsearch_index() public

By using binary search, finds an index of a value from this array which meets the given condition in O(log n) where n is the size of the array.

It supports two modes, depending on the nature of the block and they are exactly the same as in the case of #bsearch method with the only difference being that this method returns the index of the element instead of the element itself. For more details consult the documentation for #bsearch.

Show source

static VALUE
rb_ary_bsearch_index(VALUE ary)
{
    long low = 0, high = RARRAY_LEN(ary), mid;
    int smaller = 0, satisfied = 0;
    VALUE v, val;

    RETURN_ENUMERATOR(ary, 0, 0);
    while (low < high) {
        mid = low + ((high - low) / 2);
        val = rb_ary_entry(ary, mid);
        v = rb_yield(val);
        if (FIXNUM_P(v)) {
            if (v == INT2FIX(0)) return INT2FIX(mid);
            smaller = (SIGNED_VALUE)v < 0; /* Fixnum preserves its sign-bit */
        }
        else if (v == Qtrue) {
            satisfied = 1;
            smaller = 1;
        }
        else if (v == Qfalse || v == Qnil) {
            smaller = 0;
        }
        else if (rb_obj_is_kind_of(v, rb_cNumeric)) {
            const VALUE zero = INT2FIX(0);
            switch (rb_cmpint(rb_funcallv(v, id_cmp, 1, &zero), v, zero)) {
              case 0: return INT2FIX(mid);
              case 1: smaller = 1; break;
              case -1: smaller = 0;
            }
        }
        else {
            rb_raise(rb_eTypeError, "wrong argument type %"PRIsVALUE
                     " (must be numeric, true, false or nil)",
                     rb_obj_class(v));
        }
        if (smaller) {
            high = mid;
        }
        else {
            low = mid + 1;
        }
    }
    if (!satisfied) return Qnil;
    return INT2FIX(low);
}

bsearch_index

Related methods

Flowdock - Team Inbox With Chat for Software Developers