-
-
Notifications
You must be signed in to change notification settings - Fork 1.6k
/
bsearch.cr
121 lines (106 loc) · 3.16 KB
/
bsearch.cr
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
{% for p in [64, 32] %}
# Cast integer as floating number value with keeping binary structure.
private def int_as_float(i : Int{{ p }})
# Integer uses two's complement to represent signed number, but
# floating number value uses sign bit. This difference causes a
# problem that it reproduce incorrect value when you sum positive
# number and negative number. It fixes this problem.
if i < 0
i = -i
-i.unsafe_as(Float{{ p }})
else
i.unsafe_as(Float{{ p }})
end
end
# Cast floating number value as integer with keeping binary structure.
private def float_as_int(f : Float{{ p }})
if f < 0
f = -f
-f.unsafe_as(Int{{ p }})
else
f.unsafe_as(Int{{ p }})
end
end
private def bsearch_internal(from : Float{{ p }}, to, exclusive, &block)
bsearch_internal from, to.to_f{{ p }}, exclusive do |value|
yield value
end
end
private def bsearch_internal(from, to : Float{{ p }}, exclusive)
bsearch_internal from.to_f{{ p }}, to, exclusive do |value|
yield value
end
end
private def bsearch_internal(from : Float{{ p }}, to : Float{{ p }}, exclusive)
from = float_as_int from
to = float_as_int to
to -= 1 if exclusive
bsearch_internal(from, to, false){ |i| yield int_as_float i }
.try{ |i| int_as_float i }
end
private def bsearch_internal(from : Int{{ p }}, to : Int{{ p }}, exclusive)
saved_to = to
satisfied = nil
while from < to
mid = (from < 0) == (to < 0) ? from + (to - from) / 2
: (from < -to) ? -((- from - to - 1) / 2 + 1) : (from + to) / 2
if yield mid
satisfied = mid
to = mid
else
from = mid + 1
end
end
if !exclusive && from == saved_to && yield from
satisfied = from
end
satisfied
end
{% end %}
struct Range(B, E)
# By using binary search, returns the first value
# for which the passed block returns `true`.
#
# If the block returns `false`, the finding value exists
# behind. If the block returns `true`, the finding value
# is itself or exists infront.
#
# ```
# (0..10).bsearch { |x| x >= 5 } # => 5
# (0..Float64::INFINITY).bsearch { |x| x ** 4 >= 256 } # => 4
# ```
#
# Returns `nil` if the block didn't return `true` for any value.
def bsearch
from = self.begin
to = self.end
# If the range consists of floating value,
# it uses specialized implementation for floating value.
# This implementation is very fast. For example,
# `(1..1e300).bsearch{ false }` loops over 2000 times in
# popular implementation, but in this implementation loops 65 times
# at most.
{% for v in %w(from to) %}
if {{ v.id }}.is_a?(Float::Primitive)
return bsearch_internal from, to, self.excludes_end? do |value|
yield value
end
end
{% end %}
saved_to = to
satisfied = nil
while from < to
mid = from + (to - from) / 2
if yield mid
satisfied = mid
to = mid
else
from = mid + 1
end
end
if !self.excludes_end? && from == saved_to && yield from
satisfied = from
end
satisfied
end
end