https://redmine.ruby-lang.org/https://redmine.ruby-lang.org/favicon.ico?17113305112010-06-25T08:08:56ZRuby Issue Tracking SystemRuby master - Feature #3479: Array#binary_find et alhttps://redmine.ruby-lang.org/issues/3479?journal_id=119182010-06-25T08:08:56Zshyouhei (Shyouhei Urabe)shyouhei@ruby-lang.org
<ul></ul><p>=begin<br>
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.</p>
<p>As a standard API's behaviour "input is always sorted" kind of assumption is hard to accept I think.<br>
=end</p> Ruby master - Feature #3479: Array#binary_find et alhttps://redmine.ruby-lang.org/issues/3479?journal_id=119252010-06-25T14:01:30Zrogerdpack (Roger Pack)rogerpack2005@gmail.com
<ul></ul><p>=begin<br>
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.</p>
<blockquote>
<blockquote>
<p>As a standard API's behaviour "input is always sorted" kind of assumption is hard to accept I think.</p>
</blockquote>
</blockquote>
<p>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.</p>
<p>Another option might be to freeze the array once it's sorted. Something like Array#sort_and_freeze</p>
<p>class Array<br>
def sort_and_freeze!<br>
@sorted = true<br>
sort!<br>
freeze<br>
end<br>
end</p>
<p>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.<br>
Thoughts?<br>
-rp<br>
=end</p> Ruby master - Feature #3479: Array#binary_find et alhttps://redmine.ruby-lang.org/issues/3479?journal_id=119272010-06-25T14:52:37Zshyouhei (Shyouhei Urabe)shyouhei@ruby-lang.org
<ul></ul><p>=begin<br>
The problem on sort-and-freeze menu is that in Ruby sorting function might differ every time. e.g.</p>
<p>%w"1 70 a3".sort_and_freeze! {|i| i.to_i(16) }.binary_find {|i| i.to_s == "70" }</p>
<p>won't work. Yes the example above is a bit impractical, but illustrates the difficulty on it.<br>
=end</p> Ruby master - Feature #3479: Array#binary_find et alhttps://redmine.ruby-lang.org/issues/3479?journal_id=247282012-03-18T17:27:34Znahi (Hiroshi Nakamura)nakahiro@gmail.com
<ul><li><strong>Description</strong> updated (<a title="View differences" href="/journals/24728/diff?detail_id=18031">diff</a>)</li><li><strong>Assignee</strong> set to <i>mame (Yusuke Endoh)</i></li></ul><p>Endoh-san, how do you think?</p> Ruby master - Feature #3479: Array#binary_find et alhttps://redmine.ruby-lang.org/issues/3479?journal_id=248682012-03-18T18:46:38Zshyouhei (Shyouhei Urabe)shyouhei@ruby-lang.org
<ul><li><strong>Status</strong> changed from <i>Open</i> to <i>Assigned</i></li></ul> Ruby master - Feature #3479: Array#binary_find et alhttps://redmine.ruby-lang.org/issues/3479?journal_id=250082012-03-21T21:13:38Zmame (Yusuke Endoh)mame@ruby-lang.org
<ul></ul><p>Hello,</p>
<p>2012/3/18, nahi <a href="mailto:nakahiro@gmail.com" class="email">nakahiro@gmail.com</a>:</p>
<blockquote>
<p>Endoh-san, how do you think?</p>
</blockquote>
<p>Thank you for reminding this.<br>
I think this is a duplicate (or a subset) of <a class="issue tracker-2 status-5 priority-4 priority-default closed" title="Feature: Range#bsearch (Closed)" href="https://redmine.ruby-lang.org/issues/4766">#4766</a> which is accepted by matz.<br>
So I'm going to commit my patch within a reasonable period of time :-)</p>
<p>--<br>
Yusuke Endoh <a href="mailto:mame@tsg.ne.jp" class="email">mame@tsg.ne.jp</a></p> Ruby master - Feature #3479: Array#binary_find et alhttps://redmine.ruby-lang.org/issues/3479?journal_id=329082012-11-15T11:37:06Zmame (Yusuke Endoh)mame@ruby-lang.org
<ul><li><strong>Status</strong> changed from <i>Assigned</i> to <i>Closed</i></li></ul><p>This issue was solved with changeset r37655.<br>
Yusuke, thank you for reporting this issue.<br>
Your contribution to Ruby is greatly appreciated.<br>
May Ruby be with you.</p>
<hr>
<ul>
<li>
<p>array.c (rb_ary_bsearch): add Array#bsearch for binary search.<br>
<a href="/issues/4766">[ruby-core:36390]</a> [Feature <a class="issue tracker-2 status-5 priority-4 priority-default closed" title="Feature: Range#bsearch (Closed)" href="https://redmine.ruby-lang.org/issues/4766">#4766</a>]</p>
</li>
<li>
<p>test/ruby/test_array.rb: add a test for above.</p>
</li>
<li>
<p>range.c (range_bsearch): add Range#bsearch for binary search.<br>
<a href="/issues/4766">[ruby-core:36390]</a> [Feature <a class="issue tracker-2 status-5 priority-4 priority-default closed" title="Feature: Range#bsearch (Closed)" href="https://redmine.ruby-lang.org/issues/4766">#4766</a>]</p>
</li>
<li>
<p>test/ruby/test_range.rb: add a test for above</p>
</li>
<li>
<p>NEWS: added the two new methods.</p>
</li>
</ul>