読者です 読者をやめる 読者になる 読者になる

二分探索

Rubyアルゴリズムの勉強してます。 元ネタはプログラミングコンテスト攻略のためのアルゴリズムとデータ構造です。

def binary_search(ary, key)
    left = 0
    right = ary.size
    while left < right do
        mid = (left + right) / 2
        return true if key == ary[mid]
        if key > ary[mid]
            left = mid + 1
        elsif key < ary[mid]
            right = mid
        end
    end
    return false
end

sum = 0
n = gets.to_i
ary = gets.split(" ").map(&:to_i)
q = gets.to_i
gets.split(" ").map(&:to_i).each do |x|
    sum += 1 if binary_search(ary, x)
end

puts sum