我有一个排序的唯一数组,并希望有效地插入一个不在数组中的元素,如下所示:
a = [1,2,4,5,6]
new_elm = 3
insert_at = a.bsearch_index {|x| x > new_elm } # => 2
a.insert(insert_at, new_elm) # now a = [1,2,3,4,5,6]
该方法bsearch_index不存在:only bsearch,返回匹配元素而不是匹配元素的索引.有没有内置的方法来实现这一目标？
给定一个元素和一个数组,Ruby #index方法返回数组中元素的位置.我使用二进制搜索实现了自己的索引方法,期望我的索引方法优于内置索引方法.令我惊讶的是,内置的一个在实验中的速度大约是我的三倍.
任何Rubyist都知道原因吗？
数组中二进制搜索的基本思想很简单,但如果搜索无法找到确切的项目,它可能会返回"近似"索引.(我们有时可能会返回一个值大于或小于搜索值的索引).
为了寻找确切的插入点,似乎在得到大致的位置后,我们可能需要向左或向右"扫描"确切的插入位置,所以,比如说,在Ruby中,我们可以做 arr.insert(exact_index, value)
我有以下解决方案,但部件处理时begin_index >= end_index有点乱.我想知道是否可以使用更优雅的解决方案？
(如果找到完全匹配,此解决方案不关心扫描多个匹配,因此为完全匹配返回的索引可能指向与该值对应的任何索引...但我认为如果它们都是整数,我们a - 1我们知道找到完全匹配后,可以随时搜索,找到左边界,或搜索a + 1右边界.)
我的解决方案
DEBUGGING = true
def binary_search_helper(arr, a, begin_index, end_index)
middle_index = (begin_index + end_index) / 2
puts "a = #{a}, arr[middle_index] = #{arr[middle_index]}, " +
"begin_index = #{begin_index}, end_index = #{end_index}, " +
"middle_index = #{middle_index}" if DEBUGGING
if arr[middle_index] == a
return middle_index
elsif begin_index >= end_index
index = [begin_index, end_index].min
return index if a < arr[index] && index >= 0 …嗯..还不能读这个..但是 Ruby Array#assoc 是否使用线性搜索？
rb_ary_assoc(VALUE ary, VALUE key)
{
long i;
VALUE v;
for (i = 0; i < RARRAY_LEN(ary); ++i) {
v = rb_check_array_type(RARRAY_PTR(ary)[i]);
if (!NIL_P(v) && RARRAY_LEN(v) > 0 &&
rb_equal(RARRAY_PTR(v)[0], key))
return v;
}
return Qnil;
}