かべぎわブログ

ブログです

再帰２分探索 

def binary_search(max_index, min_index):
  mid_index = (max_index + min_index) // 2
  if array[mid_index] == value:
    return(mid_index)
  return(binary_search(mid_index - 1, min_index) \
    if value < array[mid_index] else binary_search(max_index, mid_index + 1))

if __name__ == '__main__':
  array = [1,3,5,11,12,13,17,22,25,28,]
  value = 28
  min_index = 0
  max_index = len(array) - 1

  print(binary_search(max_index,min_index))

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

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

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

答えはO(log n)

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

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

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

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

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

これ

なっとく！アルゴリズム

なっとく！アルゴリズム