[ruby-core:111791] [Ruby master Feature#19075] Add Array#bsearch_last and #bsearch_last_index

Issue #19075 has been updated by kyanagi (Kouhei Yanagita).


I have thought about this issue and am now leaning toward `bsearch(target: :last)`.

I proposed `bsearch_last` at first, this is because I didn't think of an optional keyword argument for `bsearch`.
Since searching the beginning and the end are the same binary searching, it seems better to call them by the same name.

Let's think about the arguments.

Consider the possibility of further arguments, keyword arguments would be better than positional argunents.

What name should the keyword arguments be?

`reverse: true` is attractive in that it allows the same name to be used for various methods,
but I don't think `bsearch(reverse: true)` clearly expresses the intent of looking for the last element.
The general word "reverse" seems to be vague to indicate the intent of "whether the target is the first one or the last one".

I think `bsearch(target: :first)` and `bsearch(target: :last)` are the best names that convey the intent.

### About find-any mode

If we adopt `bsearch(target: :last)`, I think the option (3) is the best choice.


----------------------------------------
Feature #19075: Add Array#bsearch_last and #bsearch_last_index
https://bugs.ruby-lang.org/issues/19075#change-101202

* Author: kyanagi (Kouhei Yanagita)
* Status: Open
* Priority: Normal
----------------------------------------
PR: https://github.com/ruby/ruby/pull/6611

(I'm going to talk about `Array` here, but the same argument can be made for `Range`. If `Array#bsearch_last` is acceptable, I will work also for `Range`.)

Ruby's bsearch returns the first element which satisfies the given block.

```ruby
# Search the first element greater than 18
array = [10, 15, 20, 25]
array.bsearch { |x| x > 18 } # => 20
```

If we want the last element, we need to invert the condition and step backward.

```ruby
# Search the last element less than 18
array = [10, 15, 20, 25]
index = array.bsearch_index { |x| !(x < 18) }
array[index-1] # => 15
```

Of course, we need to consider `nil` and the boundary.

```ruby
# Search the last element less than 100
index = array.bsearch_index { |x| !(x < 100) } # => nil
if index.nil?
  array.last # => 25
else
  array[index-1]
end
```

```ruby
# Search the last element less than 0
index = array.bsearch_index { |x| !(x < 0) } # => 0
if index.nil?
  array.last
elsif index == 0
  nil
else
  array[index-1]
end
```

This is where mistakes can easily be made, so I propose `Array#bsearch_last` and `Array#bsearch_last_index`.

`Array#bsearch_last` returns the last element which satisfies the given block.

`Array#bsearch` requires that all false-evaluating elements precede all true-evaluating elements. As is clear from the meaning of the method, conversely to `bsearch`, `bsearch_last` requires that all true-evaluating elements precede all false-evaluating elements. (If `bsearch_last` is acceptable, the name "find-minimum mode" should be changed.)

```ruby
array = [10, 15, 20, 25]
array.bsearch_last { |x| x < 18 }  # => 15
array.bsearch_last { |x| x < 100 } # => 25
array.bsearch_last { |x| x < 0 }   # => nil
```

There are several possible options for find-any mode.

(1) `bsearch_last` does not support find-any mode.

A block for `bsearch_last` must return `true`, `false` or `nil`.

```
[1, 2, 3].bsearch_last { 0 } # => TypeError
```

My pull request tentatively includes this implementation.

(2) `bsearch_last` supports find-any mode and it behaves like `bsearch`.

`bsearch` with find-any mode returns an element, for which the block returns zero.
If multiple elements satisfy the condition, it is not determined which of them will be returned.

It is conceivable that `bsearch_last` behaves in the same way as `bsearch`.

```
# current behavior
# It is not specified whether `:b`, `:c`, or `:d` is returned.
[[1,:a], [2, :b], [2, :c], [2, :d], [3, :e]].bsearch { |a, b| 2 <=> a } # => [2, :c]
```

(3) `bsearch_last` supports find-any mode and returns the last element. Make `bsearch` return the first element.

Change the behavior of `bsearch` to return the first element for which the block returns zero.
`bsearch_last` returns the last element for which the block returns zero.

```
# Change it like this:
[[1,:a], [2, :b], [2, :c], [2, :d], [3, :e]].bsearch { |a, b| 2 <=> a } # => [2, :b]
[[1,:a], [2, :b], [2, :c], [2, :d], [3, :e]].bsearch_last { |a, b| 2 <=> a } # => [2, :d]
```

(If this option is adopted, the name "find-any mode" should be renamed.)




-- 
https://bugs.ruby-lang.org/
 ______________________________________________
 ruby-core mailing list -- [e-mail]
 To unsubscribe send an email to [e-mail]
 ruby-core info -- https://ml.ruby-lang.org/mailman3/postorius/lists/ruby-core.ml.ruby-lang.org/