Feature #3479

Array#binary_find et al

Added by Roger Pack about 5 years ago. Updated over 2 years ago.

Status:Closed
Priority:Normal
Assignee:Yusuke Endoh

Description

=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


Related issues

Duplicates Ruby trunk - Feature #4766: Range#bsearch Closed 05/23/2011

History

#1 Updated by Shyouhei Urabe about 5 years ago

=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

#2 Updated by Roger Pack about 5 years ago

=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

#3 Updated by Shyouhei Urabe about 5 years ago

=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

#4 Updated by Hiroshi Nakamura over 3 years ago

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

Endoh-san, how do you think?

#5 Updated by Shyouhei Urabe over 3 years ago

  • Status changed from Open to Assigned

#6 Updated by Yusuke Endoh over 3 years ago

Hello,

2012/3/18, nahi nakahiro@gmail.com:

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 mame@tsg.ne.jp

#7 Updated by Yusuke Endoh over 2 years ago

  • 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.
    [Feature #4766]

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

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

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

  • NEWS: added the two new methods.

Also available in: Atom PDF