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. They are
exactly the same as in the case of the #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);
}