Gecko [ beriskala.com ]

Name	Size	Permission	Date
images	[ DIR ]	drwxr-xr-x	2026-05-01 04:23
irb	[ DIR ]	drwxr-xr-x	2026-05-01 04:23
pty	[ DIR ]	drwxr-xr-x	2026-05-01 04:23
syntax	[ DIR ]	drwxr-xr-x	2026-05-01 04:23
ChangeLog	2.29 MB	-rw-r--r--	2025-03-26 07:50
ChangeLog-0.06_to_0.52	46.51 KB	-rw-r--r--	2025-03-26 07:50
ChangeLog-0.50_to_0.60	18.81 KB	-rw-r--r--	2025-03-26 07:50
ChangeLog-0.60_to_1.1	129.14 KB	-rw-r--r--	2025-03-26 07:50
ChangeLog-1.8.0	728.09 KB	-rw-r--r--	2025-03-26 07:50
ChangeLog-1.9.3	2.86 MB	-rw-r--r--	2025-03-26 07:50
ChangeLog-2.0.0	830.16 KB	-rw-r--r--	2025-03-26 07:50
ChangeLog-2.1.0	603.56 KB	-rw-r--r--	2025-03-26 07:50
ChangeLog-2.2.0	401.16 KB	-rw-r--r--	2025-03-26 07:50
ChangeLog-2.3.0	400.76 KB	-rw-r--r--	2025-03-26 07:50
ChangeLog-2.4.0	327.98 KB	-rw-r--r--	2025-03-26 07:50
ChangeLog-YARV	144.68 KB	-rw-r--r--	2025-03-26 07:50
NEWS-1.8.7	14.22 KB	-rw-r--r--	2025-03-26 07:50
NEWS-1.9.1	15.54 KB	-rw-r--r--	2025-03-26 07:50
NEWS-1.9.2	12.07 KB	-rw-r--r--	2025-03-26 07:50
NEWS-1.9.3	9.76 KB	-rw-r--r--	2025-03-26 07:50
NEWS-2.0.0	18.01 KB	-rw-r--r--	2025-03-26 07:50
NEWS-2.1.0	11.97 KB	-rw-r--r--	2025-03-26 07:50
NEWS-2.2.0	11.47 KB	-rw-r--r--	2025-03-26 07:50
NEWS-2.3.0	12.63 KB	-rw-r--r--	2025-03-26 07:50
NEWS-2.4.0	11.31 KB	-rw-r--r--	2025-03-26 07:50
NEWS-2.5.0	16.7 KB	-rw-r--r--	2025-03-26 07:50
NEWS-2.6.0	17.87 KB	-rw-r--r--	2025-03-26 07:50
NEWS-2.7.0	24.5 KB	-rw-r--r--	2025-03-26 07:50
NEWS-3.0.0.md	24.11 KB	-rw-r--r--	2025-03-26 07:50
README.md	6.91 KB	-rw-r--r--	2025-03-26 07:50
bsearch.rdoc	4.24 KB	-rw-r--r--	2025-03-26 07:50
bug_triaging.rdoc	4.04 KB	-rw-r--r--	2025-03-26 07:50
case_mapping.rdoc	3.08 KB	-rw-r--r--	2025-03-26 07:50
contributing.rdoc	15.79 KB	-rw-r--r--	2025-03-26 07:50
dig_methods.rdoc	2.57 KB	-rw-r--r--	2025-03-26 07:50
documentation_guide.rdoc	10.7 KB	-rw-r--r--	2025-03-26 07:50
dtrace_probes.rdoc	7.42 KB	-rw-r--r--	2025-03-26 07:50
extension.ja.rdoc	72.4 KB	-rw-r--r--	2025-03-26 07:50
extension.rdoc	72.15 KB	-rw-r--r--	2025-03-26 07:50
fiber.md	6.74 KB	-rw-r--r--	2025-03-26 07:50
forwardable.rd.ja	2.34 KB	-rw-r--r--	2025-03-26 07:50
globals.rdoc	4.33 KB	-rw-r--r--	2025-03-26 07:50
hacking.md	1.88 KB	-rw-r--r--	2025-03-26 07:50
implicit_conversion.rdoc	5.5 KB	-rw-r--r--	2025-03-26 07:50
keywords.rdoc	4.63 KB	-rw-r--r--	2025-03-26 07:50
maintainers.rdoc	10.65 KB	-rw-r--r--	2025-03-26 07:50
make_cheatsheet.md	2.55 KB	-rw-r--r--	2025-03-26 07:50
marshal.rdoc	11.51 KB	-rw-r--r--	2025-03-26 07:50
memory_view.md	6.51 KB	-rw-r--r--	2025-03-26 07:50
ractor.md	26.16 KB	-rw-r--r--	2025-03-26 07:50
regexp.rdoc	30 KB	-rw-r--r--	2025-03-26 07:50
ruby-exercise.stp	1.08 KB	-rw-r--r--	2025-04-28 20:58
security.rdoc	5.72 KB	-rw-r--r--	2025-03-26 07:50
signals.rdoc	3.33 KB	-rw-r--r--	2025-03-26 07:50
standard_library.rdoc	5.77 KB	-rw-r--r--	2025-03-26 07:50
syntax.rdoc	1.21 KB	-rw-r--r--	2025-03-26 07:50
yarvarch.en	106 B	-rw-r--r--	2025-03-26 07:50
yarvarch.ja	16.41 KB	-rw-r--r--	2025-03-26 07:50

Rename

== Binary Searching

A few Ruby methods support binary searching in a collection:

Array#bsearch:: Returns an element selected via a binary search
                as determined by a given block.
Array#bsearch_index:: Returns the index of an element selected via a binary search
                      as determined by a given block.
Range#bsearch:: Returns an element selected via a binary search
                as determined by a given block.

Each of these methods returns an enumerator if no block is given.

Given a block, each of these methods returns an element (or element index) from +self+
as determined by a binary search.
The search finds an element of +self+ which meets
the given condition in <tt>O(log n)</tt> operations, where +n+ is the count of elements.
+self+ should be sorted, but this is not checked.

There are two search modes:

Find-minimum mode:: method +bsearch+ returns the first element for which
                    the block returns +true+;
                    the block must return +true+ or +false+.
Find-any mode:: method +bsearch+ some element, if any, for which
                the block returns zero.
                the block must return a numeric value.

The block should not mix the modes by sometimes returning +true+ or +false+
and other times returning a numeric value, but this is not checked.

<b>Find-Minimum Mode</b>

In find-minimum mode, the block must return +true+ or +false+.
The further requirement (though not checked) is that
there are no indexes +i+ and +j+ such that:

- <tt>0 <= i < j <= self.size</tt>.
- The block returns +true+ for <tt>self[i]</tt> and +false+ for <tt>self[j]</tt>.

Less formally: the block is such that all +false+-evaluating elements
precede all +true+-evaluating elements.

In find-minimum mode, method +bsearch+ returns the first element
for which the block returns +true+.

Examples:

a = [0, 4, 7, 10, 12]
  a.bsearch {|x| x >= 4 } # => 4
  a.bsearch {|x| x >= 6 } # => 7
  a.bsearch {|x| x >= -1 } # => 0
  a.bsearch {|x| x >= 100 } # => nil

r = (0...a.size)
  r.bsearch {|i| a[i] >= 4 } #=> 1
  r.bsearch {|i| a[i] >= 6 } #=> 2
  r.bsearch {|i| a[i] >= 8 } #=> 3
  r.bsearch {|i| a[i] >= 100 } #=> nil
  r = (0.0...Float::INFINITY)
  r.bsearch {|x| Math.log(x) >= 0 } #=> 1.0

These blocks make sense in find-minimum mode:

a = [0, 4, 7, 10, 12]
  a.map {|x| x >= 4 } # => [false, true, true, true, true]
  a.map {|x| x >= 6 } # => [false, false, true, true, true]
  a.map {|x| x >= -1 } # => [true, true, true, true, true]
  a.map {|x| x >= 100 } # => [false, false, false, false, false]

This would not make sense:

a.map {|x| x == 7 } # => [false, false, true, false, false]

In find-any mode, the block must return a numeric value.
The further requirement (though not checked) is that
there are no indexes +i+ and +j+ such that:

- <tt>0 <= i < j <= self.size</tt>.
- The block returns a negative value for <tt>self[i]</tt>
  and a positive value for <tt>self[j]</tt>.
- The block returns a negative value for <tt>self[i]</tt> and zero <tt>self[j]</tt>.
- The block returns zero for <tt>self[i]</tt> and a positive value for <tt>self[j]</tt>.

Less formally: the block is such that:

- All positive-evaluating elements precede all zero-evaluating elements.
- All positive-evaluating elements precede all negative-evaluating elements.
- All zero-evaluating elements precede all negative-evaluating elements.

In find-any mode, method +bsearch+ returns some element
for which the block returns zero, or +nil+ if no such element is found.

Examples:

a = [0, 4, 7, 10, 12]
  a.bsearch {|element| 7 <=> element } # => 7
  a.bsearch {|element| -1 <=> element } # => nil
  a.bsearch {|element| 5 <=> element } # => nil
  a.bsearch {|element| 15 <=> element } # => nil

a = [0, 100, 100, 100, 200]
  r = (0..4)
  r.bsearch {|i| 100 - a[i] } #=> 1, 2 or 3
  r.bsearch {|i| 300 - a[i] } #=> nil
  r.bsearch {|i|  50 - a[i] } #=> nil

These blocks make sense in find-any mode:

a = [0, 4, 7, 10, 12]
  a.map {|element| 7 <=> element } # => [1, 1, 0, -1, -1]
  a.map {|element| -1 <=> element } # => [-1, -1, -1, -1, -1]
  a.map {|element| 5 <=> element } # => [1, 1, -1, -1, -1]
  a.map {|element| 15 <=> element } # => [1, 1, 1, 1, 1]

This would not make sense:

a.map {|element| element <=> 7 } # => [-1, -1, 0, 1, 1]