🔍
[鉄則A11] Binary Search 1
二分探索の基本問題。
問題を要約する
- 指定の値は何番目にあるか？
非再帰版
90 ms
N, X = gets.split.collect(&:to_i) # => [15, 47]
A = gets.split.collect(&:to_i) # => [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
def bsearch_index(a, v)
l = 0
r = a.size.pred
while l <= r
m = (l + r) / 2
if a[m] == v
break m
end
if v < a[m]
r = m.pred
else
l = m.next
end
end
end
p bsearch_index(A, X).next # => 11
再帰版
92 ms
N, X = gets.split.collect(&:to_i) # => [15, 47]
A = gets.split.collect(&:to_i) # => [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
def bsearch_index(a, v, l = 0, r = a.size.pred)
if r < l
return
end
m = (l + r) / 2
if a[m] == v
return m
end
if v < a[m]
r = m.pred
else
l = m.next
end
bsearch_index(a, v, l, r)
end
p bsearch_index(A, X).next # => 11
ジャッジシステムの計算時間は ±40 ms ほどの揺らぎがあるので正しい比較はできない。
Array#bsearch_index 版
91 ms
N, X = gets.split.collect(&:to_i) # => [15, 47]
A = gets.split.collect(&:to_i) # => [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
p A.bsearch_index { |e| X - e }.next # => 11
find の代替として使うなら find-any モードが適している。
Array#bsearch_index は速い
正しくベンチマークをとれば自作より 2.25 倍速かった。
ベンチーマーク
a = 10000.times.collect { rand(10**9) }.sort
require "benchmark/ips"
Benchmark.ips do |x|
x.report("bsearch_index") { bsearch_index(a, rand(10**9)) }
x.report("Array#bsearch_index") { v = rand(10**9); a.bsearch_index { |e| v - e } }
x.compare!
end
# Warming up --------------------------------------
# bsearch_index 72.878k i/100ms
# Array#bsearch_index 163.756k i/100ms
# Calculating -------------------------------------
# bsearch_index 729.285k (± 0.3%) i/s - 3.717M in 5.096517s
# Array#bsearch_index 1.644M (± 0.3%) i/s - 8.352M in 5.078638s
#
# Comparison:
# Array#bsearch_index: 1644458.8 i/s
# bsearch_index: 729285.0 i/s - 2.25x slower
Discussion