2分検索

2分検索

解説

配列の要素が、あらかじめ昇順あるいは降順にソートされているときに

そこから目的の値を探し出す有効なアルゴリズム。


配列の要素数がNの時、最大でもlog_2 N回のループで探索が終了する。



例えば、ある人が100までの数字のうち1つを思い浮かべて、

それを別の人が当てるゲームを考えてみる。


「それは50より大きい?」

とたずねて、

「いや、もっと小さい」

と言ったら、これで探索範囲が半分になる。

この調子で、

「25より大きい?」 「そうだね」

「37より大きい?」 「いや、小さいよ」

と聞いていけば、

「それは1?」「違う」「それは2?」「違う」・・・・

と聞いていくより遥かに少ない回数で数を当ててやることができる(場合にもよるが)。

これが2分検索である。


# arrayの中にtargetが含まれているかどうか
def binary_search(array, target)

  first = 0                 # 先頭のインデックス
  last = array.length - 1   # 末尾のインデックス
  
  while(first <= last)
    center = (first + last) / 2    # 中央のインデックス
    if(array[center] == target)    # もし値が合えば真を返す
      return true
    elsif(array[center] > target)  # 半分より上
      last = center - 1
    else                           # 半分より下
      first = center + 1
    end
  end
  
  # 見つからなければ偽を返す
  return false

end

p binary_search([4, 13, 19, 31, 45, 55, 72, 86, 98], 19)  #=> true
p binary_search([4, 13, 19, 31, 45, 55, 72, 86, 98], 77)  #=> false

これはあくまで例であり、普段はinclude?で一発である。