Rubyの二分探索(dichotomous search)アルゴリズムの簡単な例

コンピュータサイエンスにおいて、二分探索、対数探索とも呼ばれる二項探索は、順序配列の中から特定の要素を見つけ出すための探索アルゴリズムである。探索は配列の中央の要素から始まり、中央の要素がまさに見つけたい要素であれば終了し、特定の要素が中央の要素より大きいか小さい場合は、中央の要素より大きいか小さい配列の半分で探索し、比較は最初と同じく中央の要素から始めます。あるステップで配列が空であれば、見つからなかったということです。この検索アルゴリズムでは、比較のたびに検索対象が半分に絞られます。

複雑性解析
<スパン 時間の複雑さ
半分に折りたたむと、毎回探索領域が半分になり、時間複雑度は . (nは集合の要素数)
<スパン 空間の複雑さ。
は再帰的に定義されているが、尾再帰的であり、ループとして書き換えることができる。

Rubyコード例

def binseaech(arr, i)
  low, high = 0, arr.size - 1
  while (low < high)
    mid = (low + high)/2
    if arr[mid] < i
      low = mid + 1
    elsif arr[mid] > i
      high = mid - 1
    else
      return mid
    end
  end
end

arr = [1,3,12,34,35,46,91,108]
puts binseaech(arr, 91)

結果

6
[Finished in 0.1s]