1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
=begin
= Ruby/Bsearch: a binary search library for Ruby
Ruby/Bsearch is a binary search library for Ruby. It can search the FIRST or
LAST occurrence in an array with a condition given by a block.
Tha latest version of Ruby/Bsearch is available at
((<URL:http://namazu.org/~satoru/ruby-bsearch/>))
.
== Example
% irb -r ./bsearch.rb
>> %w(a b c c c d e f).bsearch_first {|x| x <=> "c"}
=> 2
>> %w(a b c c c d e f).bsearch_last {|x| x <=> "c"}
=> 5
>> %w(a b c e f).bsearch_first {|x| x <=> "c"}
=> 2
>> %w(a b e f).bsearch_first {|x| x <=> "c"}
=> nil
>> %w(a b e f).bsearch_last {|x| x <=> "c"}
=> nil
>> %w(a b e f).bsearch_lower_boundary {|x| x <=> "c"}
=> 2
>> %w(a b e f).bsearch_upper_boundary {|x| x <=> "c"}
=> 2
>> %w(a b c c c d e f).bsearch_range {|x| x <=> "c"}
=> 2...5
>> %w(a b c d e f).bsearch_range {|x| x <=> "c"}
=> 2...3
>> %w(a b d e f).bsearch_range {|x| x <=> "c"}
=> 2...2
== Illustration
<<< figure
== API
--- Array#bsearch_first (range = 0 ... self.length) {|x| ...}
Return the index of the FIRST occurrence in an array with a condition given
by block. Return nil if not found. Optional parameter `range' specifies the
range of searching.
To search an ascending order array, let the block be like {|x| x <=> key}.
To search an descending order array, let the block be like {|x| key <=> x}.
Naturally, the array should be sorted in advance of searching.
--- Array#bsearch_last (range = 0 ... self.length) {|x| ...}
Return the index of the LAST occurrence in an
array with a condition given by block. Return nil if not
fount. Optional parameter `range' specifies the range of searching.
To search an ascending order array, let the block be like {|x| x <=> key}.
To search an descending order array, let the block be like {|x| key <=> x}.
Naturally, the array should be sorted in advance of searching.
--- Array#bsearch_lower_boundary (range = 0 ... self.length) {|x| ...}
Return the LOWER boundary in an array with a condition given
by block. Optional parameter `range' specifies the
range of searching.
To search an ascending order array, let the block be like {|x| x <=> key}.
To search an descending order array, let the block be like {|x| key <=> x}.
Naturally, the array should be sorted in advance of searching.
--- Array#bsearch_upper_boundary (range = 0 ... self.length) {|x| ...}
Return the UPPER boundary in an array with a condition
given by block. Optional parameter `range' specifies the
range of searching.
To search an ascending order array, let the block be like {|x| x <=> key}.
To search an descending order array, let the block be like {|x| key <=> x}.
Naturally, the array should be sorted in advance of searching.
--- Array#bsearch_range (range = 0 ... self.length) {|x| ...}
Return both the LOWER and the UPPER boundaries in an array with a condition
given by block as Range object. Optional parameter
`range' specifies the range of searching.
To search an ascending order array, let the block be like {|x| x <=> key}.
To search an descending order array, let the block be like {|x| key <=> x}.
Naturally, the array should be sorted in advance of searching.
--- Array#bsearch (range = 0 ... self.length) {|x| ...}
This is an alias to Array#bsearch_first.
== Download
Ruby/Bsearch is a free software with ABSOLUTELY NO WARRANTY
under the terms of Ruby's licence.
* ((<URL:http://namazu.org/~satoru/ruby-bsearch/ruby-bsearch-1.4.tar.gz>))
* ((<URL:http://cvs.namazu.org/ruby-bsearch/>))
satoru@namazu.org
=end
|
