2分探索っぽいものを実装した[Ruby]

はじめに

競技プログラミングをやっていたら、小さい順に並んだ無数の自然数の配列中(重複は無い)から、与えられたターゲットが配列のどの数とどの数の間にあるのか実装する必要があった。
無作為に0から探していくと実行時間切れになったので、2分探索っぽい実装をして効率的に探索を行おうとした。

計算量

配列の全ての要素に対して探索を行う場合には、計算量が配列の要素数に比例して大きくなる。つまりオーダー記法で書くとO(N)

これに対して、二分探索を行うと、計算量はO(logN) (2分探索では対数の底は2)となるので、要素数が増えたときにも計算量の増加は比較的少なく済む。

これなら時間内に実行時間内に探索が終わりそう。

実装

とりあえず実装

色々と未熟な点があると思いますので、ご指摘があればコメントいただけるとありがたいです。

array = [1, 4, 6, 8, 20, 34, 87, 118, 234, 769, 1000, 8909] # 自然数の配列(ソート済み)
target = 48 #ターゲットとなる自然数
outputs = "配列の範囲外です"

# targetが配列の範囲内にある場合
if array.first <= target && target <= array.last
  while array.length >= 2 
    length = array.length

   # 配列の中央2つの間にあるか？
    if array[length / 2 - 1] <= target && target <= array[length / 2]
      outputs = array[length / 2 - 1].to_s + " " + array[length / 2].to_s
      break

   # 配列の前半にtargetがあるので配列の前半を切り取る
    elsif target < array[length / 2 - 1 ]
      array = array.take(length / 2)

   # 配列の後半にtargetがあるので配列の後半を切り取る
    else 
      array = array.slice(length / 2 ... length)
    end
  end
end

puts outputs

arrayにソート済みの任意の自然数を、targetに与えられた自然数を代入する。

実行すると以下のようになる。

34 87

確かに48は34と87の間なのでOK

ターゲットが配列の範囲外の場合(target = 10000000とか)には、

配列の範囲外です

と出力される。

まとめ

アルゴリズム関連の知識が乏しいのでこれを機に色々勉強する。
計算量などについても、ぼんやりとしかわからないので調べたものをまたまとめようと思う。