From: "Hanmac (Hans Mackowiak) via ruby-core" <ruby-core@...>
Date: 2024-08-26T09:07:46+00:00
Subject: [ruby-core:118958] [Ruby master Feature#20692] Rewrite Array#bsearch in Ruby

Issue #20692 has been updated by Hanmac (Hans Mackowiak).


`find_minimum_mode = finder || !finder` isn't this always true?

----------------------------------------
Feature #20692: Rewrite Array#bsearch in Ruby
https://bugs.ruby-lang.org/issues/20692#change-109530

* Author: sebyx07 (Sebastian Buza)
* Status: Open
----------------------------------------
inspired by https://bugs.ruby-lang.org/issues/20182

# Proporsal

Rewrite Array#bsearch

```ruby
class Array
  def bsearch
    return to_enum(:bsearch) { size } unless block_given?

    return nil if empty?

    low = 0
    high = size - 1
    mid = size / 2

    finder = yield(self[mid])
    find_minimum_mode = finder || !finder

    if find_minimum_mode
      while low < high
        if yield(self[mid])
          high = mid
        else
          low = mid + 1
        end
          mid = low + (high - low) / 2
      end
      yield(self[low]) ? self[low] : nil
    else
      while low <= high
        case yield(self[mid])
        when 0
          return self[mid]
        when 1
          high = mid - 1
        when -1
          low = mid + 1
        else
          raise TypeError, 'wrong argument type (must be -1, 0, 1, true, or false)'
        end
        mid = low + (high - low) / 2
      end
      nil
    end
  end
end
```

https://github.com/sebyx07/native_ruby/blob/master/lib/native_ruby/array/bsearch.rb

I also created this gem:
https://github.com/sebyx07/native_ruby/ - to load patches w/o depending on the ruby/master

## Benchmark

```
ruby 3.3.3 (2024-06-12 revision f1c7b6f435) +YJIT [x86_64-linux]

Benchmark results (average over 10000000 iterations):
                           user     system      total        real
Original bsearch:     12.329160   0.009148  12.338308 ( 12.337310)
Native bsearch:        3.437350   0.000057   3.437407 (  3.437270)
```



-- 
https://bugs.ruby-lang.org/
 ______________________________________________
 ruby-core mailing list -- ruby-core@ml.ruby-lang.org
 To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org
 ruby-core info -- https://ml.ruby-lang.org/mailman3/lists/ruby-core.ml.ruby-lang.org/