Home > Erlang | Python > [Python]2分探索

[Python]2分探索

ビューティフルコードの7章で、この章を読み進む前に2分探索を実装しろと書いてあった。
ということでPythonで実装してみる。

最初に書いたコードはこれ。

PLAIN TEXT
PYTHON:
  1. def mybinarysearch(a, t, f):
  2.     n = len(a)
  3.     if n <= 0:
  4.         return -1
  5.     if n == 1:
  6.         if a[0] == t:
  7.             return 0
  8.         else:
  9.             return -1
  10.     m = int(n / 2)
  11.     r = f(t, a[m - 1])
  12.     if r <= 0:
  13.         x = mybinarysearch(a[:m], t, f)
  14.         if x>= 0:
  15.             return x
  16.         else:
  17.             return -1
  18.     else:
  19.         x = mybinarysearch(a[m:], t, f)
  20.         if x>= 0:
  21.             return m + x
  22.         else:
  23.             return -1

配列、検索対象、比較関数を渡す。
さすがにこれだと、いちいちlenを計算していたり効率悪すぎだし、コードも汚いのでもう少しましにする。

PLAIN TEXT
PYTHON:
  1. def mybinarysearch(a, t, f):
  2.     def func(array, i, n):
  3.         if n <= 0:
  4.             return -1
  5.         elif n == 1:
  6.             if f(array[0], t) == 0:
  7.                 return i
  8.             else:
  9.                 return -1
  10.         else:
  11.             m = int(n / 2)
  12.             if f(t, array[m - 1]) <= 0:
  13.                 return func(array[:m], i, m)
  14.             else:
  15.                 return func(array[m:], i + m, n - m)
  16.     return func(a, 0, len(a))

これで、配列中で対象に合致する最小のIndexが返るはず？

最小にこだわらなければこうなるかな

PLAIN TEXT
PYTHON:
  1. def mybinarysearch(a, t, f):
  2.     def func(array, i, n):
  3.         if n <= 0:
  4.             return -1
  5.         m = int(n / 2)
  6.         r = f(t, array[m])
  7.         if r == 0:
  8.             return i + m
  9.         elif r <0:
  10.             return func(array[:m], i, m)
  11.         else:
  12.             return func(array[m + 1:], i + m + 1, n - m - 1)
  13.     return func(a, 0, len(a))

この章の主題であるテストはまだちゃんとやってない。

これから考えてやってみよう。
再帰で書いてしまったので遅そうだけど、2分探索だったらあふれることはないだろう。

Comments:1

常山日記 08-05-13 (火) 14:59

[Python][Mercurial]巡回

第2回 Trac Lightningで簡単インストール wax 0.3.19 Pythonライブラリのインストールパス確認 Python で wave …

Comment Form
Remember personal info

Trackbacks:0

Trackback URL for this entry
http://blog.joyfullife.jp/archives/2008/05/13023417.php/trackback
Listed below are links to weblogs that reference
[Python]2分探索 from 30からのBlog

Home > Erlang | Python > [Python]2分探索

Recent Entries
Categories
Archives
Tag Cloud
Search
Feeds
Meta

Return to page top