Feature #20692
Updated by sebyx07 (Sebastian Buza) about 1 year ago
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
```
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)
```