LoginSignup
0

More than 3 years have passed since last update.

PYthon3で線形探索&二分探索書いてみた

Posted at

線形探索

Pythonのenumerate()関数を使うと、forループの中でリスト(配列)などのイテラブルオブジェクトの要素と同時にインデックス番号(カウント、順番)を取得できる。
計算時間 O(n)

def linear_search(li,ans):
    print(str(ans) + "を検索します")
    for i,data in enumerate(li):
        if data == ans:
            print(str(i)+ "番目にありました")
            break
        else:
            print("入力した要素は存在しませんでした")

if __name__ == '__main__':
    li=[1,4,5,6,8,9,14,19]
    print("調べるリスト")
    print(li)
    search_num = int(input("上のリストから調べたい要素を入力してください"))
    linear_search(li, search_num)

二分探索

計算時間 O ( log₂n )

def binary_search(li, ans):
    low = 0
    high = len(li) - 1 

    # 探索の下限のlowが上限のhighになるまで探索します。
    while low <= high:
        mid = (low + high) // 2 # 中央値
        guess = li[mid]
        if guess == ans:
            return mid
        if guess > ans:
            high = mid - 1
        else:
            low = mid + 1
    return None

li = [i for i in range(1,101)]
print(binary_search(li, 3))
print(binary_search(li, -1))

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0