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
|
# File 'lib/MARQ/util.rb', line 2
def count_smaller(value)
size = self.length
low = 0
last = size - 1
hi = size - 1
pos = size / 2
while true
case
when value == self[pos]
return pos
when pos == last && self[pos] < value
return size
when pos == 0 && value <= self[pos]
return 0
when self[pos] < value && value < self[pos + 1]
return pos + 1
when value < self[pos]
hi = pos
pos = (pos - low) / 2 + low
when self[pos] < value
low = pos
pos = (hi - pos) / 2 + pos + 1
end
end
end
|