>>71
上でも指摘されているが整っているの定義が不明
二分探査の場合は、存在しないこともlog n で確認可能だが、この手法は整っているの定義次第では存在しない者の確認が非常に時間かかる（ソートされている場合は存在するものと同等だが、そうすると二分探索よりも利点が少なくなる）
平均計算量を求めるのはちと難しそうだけど、格納される値の値域に依存するかな
たぶん、log n 程良くはないと思う