室村日記

プログラミング初心者のメモ書きです

Python3で二分探索

wikipediaに載っているc++スクリプトpythonで書き直しただけですが,”忘れた時にとりあえずコピペしたら動く”がモットーなので自分用にメモ.

[wiki:二分探索]

実装は以下.

#二分探索
def binarySearch(ary, key, imin, imax):
    if ( imax < imin ):
        return "KEY_NOT_FOUND"
    else:
        imid = imin + (imax - imin)//2
        if (ary[imid] > key):
            return binarySearch(ary, key, imin, imid - 1)
        elif (ary[imid] < key):
            return binarySearch(ary, key, imid + 1, imax)
        else:
            return imid

試してみたらちゃんと動きました.

a = [1,2,2,4,5,6,7,10,20,40]
binarySearch(a, 40, 0, len(a)-1)

再帰ってプログラミング初心者が苦しむ難関の1つですよね……