二分探索(binary search) - すぱいだー日記。

Ruby で実装してみたけどちょっと時間がかかってしまった。そんな自分に凹みんぐ。

def binary_search(target , list , l , h)
  return -1 if l > h
  i = ((h - l) / 2).floor + l
  return i if target == list[i]
  if list[i] > target
    return binary_search(target , list , l , i  -1)
  else
    return binary_search(target , list , i + 1, h )
  end
end

まっちょなブログの実装とあってたから OK だろう。

	平均	最大
線形探索	N / 2	N
二分検索	$log_{2}~N$	$log_{2}~N$ + 1

線形探索の最大比較回数 = N