From: mame@... Date: 2015-01-12T14:32:15+00:00 Subject: [ruby-core:67546] [ruby-trunk - Feature #10730] [Assigned] Implement Array#bsearch_index Issue #10730 has been updated by Yusuke Endoh. Status changed from Open to Assigned Assignee set to Yukihiro Matsumoto > Let me then tell you about my use case. Thank you, looks good to me. Also, I just noticed that Array#bsearch is weaker than C's BSEARCH(3). BSEARCH(3) returns the pointer to the array, so it effectively returns not only the value but also the index. Array#bsearch_index will make up for the weakness. I give +1 for this feature, but anyway, Matz will determine a feature proposal. Assigning to him. -- Yusuke Endoh ---------------------------------------- Feature #10730: Implement Array#bsearch_index https://bugs.ruby-lang.org/issues/10730#change-50959 * Author: Radan Skori�� * Status: Assigned * Priority: Normal * Assignee: Yukihiro Matsumoto ---------------------------------------- We currently have Array#bsearch but no Array#bsearch_index and to me it seems that violates the principle of least surprise, especially when we consider the other combinations of existing methods that find either an element or it���s index. For example: the method would be very useful when needing to slice out a part of a sorted array. It would allow very quick location of the indices of the beginning and end of the segment. A quick google of ���ruby bsearch_index��� reveals that I am not the only one that needed and expected that function to exist: http://stackoverflow.com/questions/23481725/using-bsearch-to-find-index-for-inserting-new-element-into-sorted-array http://stackoverflow.com/questions/8672472/is-there-a-built-in-binary-search-in-ruby https://github.com/tyler/binary_search#usage The very good thing is that we can get that method almost for free since the current implementation of bsearch internally finds the index and then looks up the actual element. I have opened a PR on the github mirror that adds bsearch_index in what seems to me the simplest way possible: https://github.com/ruby/ruby/pull/813 . I changed the bsearch implementation into bsearch_index and based the bsearch on it. Please Note: The diff is deceptively large, if you look carefully you will notice that the change is actually small and the actual binary search algorithm remained completely intact. I have kept the behaviour documentation on bsearch and simply referenced it from bsearch_index to minimize the documentation changes. -- https://bugs.ruby-lang.org/