二分探索サイコー!今回の場合は、探索の対象が最大512個なので、二分探索のうまみがあんまり無いかなぁ、と思う。だからハッシュとして、O(1) で検索したい気もする。
たぶん、探索対象をソートしておいて、二分探索するっていう方式を考えるっていうのはみんな意外にできなくて、単純なリニアサーチしか思いつかないと思うんですよ。pure C なので、ソート関数は用意されている(qsortね)のですが、探索用の関数って用意されていないので、自分で考えて実装しないといけなくなるわけです。そうすると、二分探索ということを思い付かなくて、リニアサーチになるということではないかと。やっぱり2005/01/23に書いた「プログラミングと体力」で書いたとおり体力が足りない。。。
実装はまだいい。少なくとも理論は分かる、というところまではいってほしいな。

コメントを残す

メールアドレスが公開されることはありません。