のだなのだ

ほげ〜

天使と悪魔と二分探索

 少し前に映画、天使と悪魔を見ました。爆弾の場所を探す時にカメルレンゴの提案でバチカンの各区画の電力を順番に落として映像の電気に変化があるかないかを探すシーンがありました。

 劇中ではたくさんある区画の電力を順番に落としていましたが、まず半分ずつ落として、映像に変化があった片方のさらに半分を落として、、、、を繰り返した方(二分探索)した方が圧倒的に速く探せるのに、、、、と感じました。

 仮に二分探索で最も効率的に探索が行える2の冪乗個、今回は128個の区画があったとすると劇中のやり方では平均64回の試行でわかることになりますが、二分探索なら8回の試行で分かってしまいます。64回で終わらないリスクを考えれば一回の試行にかかる時間が長くても二分探索を行ったほうがいいと思うんですけどね