Project

General

Profile

Actions

Feature #3479

closed

Array#binary_find et al

Added by rogerdpack (Roger Pack) almost 14 years ago. Updated over 11 years ago.

Status:
Closed
Target version:
-

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 1 (0 open1 closed)

Is duplicate of Ruby master - Feature #4766: Range#bsearchClosedmame (Yusuke Endoh)05/23/2011Actions
Actions #1

Updated by shyouhei (Shyouhei Urabe) almost 14 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

Actions #2

Updated by rogerdpack (Roger Pack) almost 14 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

Actions #3

Updated by shyouhei (Shyouhei Urabe) almost 14 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

Updated by nahi (Hiroshi Nakamura) about 12 years ago

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

Endoh-san, how do you think?

Actions #5

Updated by shyouhei (Shyouhei Urabe) about 12 years ago

  • Status changed from Open to Assigned

Updated by mame (Yusuke Endoh) about 12 years ago

Hello,

2012/3/18, nahi :

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

Actions #7

Updated by mame (Yusuke Endoh) over 11 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.
    [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.

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0