バイナリサーチ

binary search algorithm not working – StackOverflow

Python的には,標準モジュールで用意されているんだからそれを使えば良い.

import bisect

a = [1,2,5,8,23,67,345]
bisect.bisect_left(a, 5, 0, 6)

2

参考:
8.6. bisect — 配列二分法アルゴリズム – Python 3.6.1ドキュメント
 
 

実装する場合は(引数をもう少し分かり易い名前にして一般的な順番にすると),

def binarySearch(a, key, imin, imax): 
    if imin > imax:
        return -1
    imid = (imax + imin) // 2#int(imin + (imax - imin)/2)

    if a[imid] == key:
        return imid
    elif key < a[imid]:
        return binarySearch(a, key, imin, imid-1)
    else:
        return binarySearch(a, key, imid+1, imax)


binarySearch(a, 5, 0, 6)

2

pythonの整数は任意精度なので,オーバーフローは気にしなくて良いと思う.
二分探索 – Wikipedia の「実装上の間違い」について)
 
 

%timeit binarySearch(a, 5, 0, 6)
%timeit bisect.bisect_left(a, 5, 0, 6)

2.11 µs ± 197 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
555 ns ± 12.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

広告
カテゴリー: 未分類 パーマリンク

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中