Feature #3479: Array#binary_find et al

• Status: Closed
• Assignee: mame (Yusuke Endoh)
• Target version: -

[rogerdpack (Roger Pack)]

=begin
It would be quite handy to have a method for searching through an Array, when sorted, using binary search.
Apparently doing this in C would be ideal [1].
So this is a feature request for the same
Array#binary_index
Array#binary_find (or binary_search, whichever the commiter prefers).

Thanks much.
-r
[1] http://github.com/tyler/binary_search
=end

[shyouhei (Shyouhei Urabe)]

=begin
The point is, Ruby's arrays are not always sorted. You can't easily say if an array is sorted or not unless you actually scan the whole array, which is O(n) -- slower than binary search. And if you apply bsearch to non-sorted arrays it should of course fail.

As a standard API's behaviour "input is always sorted" kind of assumption is hard to accept I think.
=end

[rogerdpack (Roger Pack)]

=begin
In my case I sort an array once, then I search it frequently for certain elements later. A binary search method would be quite convenient.

As a standard API's behaviour "input is always sorted" kind of assumption is hard to accept I think.

I think it would be ok to specify the aberrant behavior "note if your array is not sorted this gives undefined results" or what not.

Another option might be to freeze the array once it's sorted. Something like Array#sort_and_freeze

class Array
def sort_and_freeze!
@sorted = true
sort!
freeze
end
end

Though for me, I'm fine with not doing this and allowing for mutable arrays, and just specify that the author must sort them first.
Thoughts?
-rp
=end

[shyouhei (Shyouhei Urabe)]

=begin
The problem on sort-and-freeze menu is that in Ruby sorting function might differ every time. e.g.

%w"1 70 a3".sort_and_freeze! {|i| i.to_i(16) }.binary_find {|i| i.to_s == "70" }

won't work. Yes the example above is a bit impractical, but illustrates the difficulty on it.
=end

[nahi (Hiroshi Nakamura)]

• Description updated (diff)
• Assignee set to mame (Yusuke Endoh)

Endoh-san, how do you think?

[shyouhei (Shyouhei Urabe)]

• Status changed from Open to Assigned

[mame (Yusuke Endoh)]

Hello,

2012/3/18, nahi [e-mail]:

Endoh-san, how do you think?

Thank you for reminding this.
I think this is a duplicate (or a subset) of #4766 which is accepted by matz.
So I'm going to commit my patch within a reasonable period of time :-)

--
Yusuke Endoh [e-mail]

[mame (Yusuke Endoh)]

• Status changed from Assigned to Closed

This issue was solved with changeset r37655.
Yusuke, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.

---

• array.c (rb_ary_bsearch): add Array#bsearch for binary search.
  [ruby-core:36390] [Feature #4766]

• test/ruby/test_array.rb: add a test for above.

• range.c (range_bsearch): add Range#bsearch for binary search.
  [ruby-core:36390] [Feature #4766]

• test/ruby/test_range.rb: add a test for above

• NEWS: added the two new methods.