ある名前があり、その人の電話番号を電話帳で調べるときの計算量

最近アルゴリズムの本を読んでいて、その中で以下の問題があった。

ある名前があり、その人の電話番号を電話帳で調べたい。このときの計算量はなにか。

答えはO(log n)

ただ、それの解説が書いていなく、しばらく悩んでいた。いろいろ考えて、ようやく答えにたどり着いた。たぶん。

なぜ計算量がO(log n)になるのか？

昔々の電話帳というのは、五十音順でいろんな人の電話番号が掲載されていた。
たとえば夏本さんの電話番号を探そうと思ったら、とりあえず電話帳の真ん中らへんを開いてみる。そしたら田中さんの電話番号がのっていた。じゃあ、「な」から始まる人はもう少し先の方のページなんだなぁと思って、更に先の方のページを適当に開く、そしたら布川さんの電話番号がのっていたので、少し行き過ぎてしまったなということですこしページを戻る。みたいな探し方をすることになるはず。

これが二分探索。ということでO(log n) だと思う。

電話帳というものがあまり想像できず、苦労した。
紙の辞書から特定の単語を探す、とかならかんたんに答えにたどり着いたかもしれない。

これ

なっとく！アルゴリズム