線形探索と二分探索の違い

線形探索

先頭から探すので遅い場合もあるが、配列をメンテする必要がないので扱いやすい。

def linear_search(a, v)
  a.size.times do |i|
    if a[i] == v
      return true
    end
  end
  false
end

linear_search([*0...100], 99)   # => true
linear_search([*0...100], 100)  # => false

二分探索

ソート済みであることが条件だが半分ずつ詰めていくため速い。

def binary_search(a, v, l = 0, r = a.size.pred)
  if r < l
    return false
  end
  m = (l + r) / 2
  if a[m] == v
    return true
  end
  if v < a[m]
    r = m.pred
  else
    l = m.succ
  end
  send(__method__, a, v, l, r)
end

binary_search([*0...100], 99)   # => true
binary_search([*0...100], 100)  # => false

計算時間

• 線形探索: O(n)
• 二分探索: O(log n)