>>69
>>70
確かにキーの最大値を求めるのは線形時間かかります。なのであらかじめ、隣接するキーの最大値が分かっているデータに使用可能です。
探索の最悪時間は線形時間ですが、平均時間はlogのオーダーになるのではないでしょうか。私が不勉強なもので理論的には、示めせませんが多分logのオーダーになると思います。
ソートしなくても探索できるのは差の絶対値を取るからです。動画に入れるのを忘れました。すいません。
計算についてはそれであっています。わざわざご指摘ありがとうございます