ゲームが作れるようになるまでがんばる日記

ゲーム制作のことを中心にゲームに関することを書いています

二分探索

二分探索はソート済みのデータ列の中から目的のデータを探し出す方法。
まずちょうど半分のところを調べて、目的のデータよりも小さければ、それよりも後にデータがあり、大きい場合はそれよりも前にあると分かる。その半分をまた同じように半分のところで調べる。このようにして探索範囲が半分ずつになっていくので、計算量はO(logN)となる。
データ列がソート済みでなければならないという制約はあるが、非常に検索が速く行える。ゲームで使うデータは予めソートした形で用意しておくか、ロードしたときにソートしておけば良い。
今、自分が書いているコードではデータの検索は頭から比較していくという何の工夫も無いもの。これを二分探索できるように書き換えることにしよう。