リスト探索をpythonで

線形探索

配列から要素を探索するアルゴリズム。
左端から順に、目的数と比較していく。

def liner_search(aList, val):
    for x in aList:
        if x == val:
            return True
    return False

2分探索

整列された配列から要素を探索するアルゴリズム。
配列の中心から目的数と比較。大小関係により、いらない側を調べなくて済む。
探索する数を半分ずつ減らしていくことで効率が上がる。

def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (low + high ) // 2 #midの更新するってとこがポイント
        if list[mid] == item:
            print('Found')
            return mid
        if list[mid] > item:
            high = mid - 1 #midより右側もういらん
        else:
            low = mid + 1 #midより左側もういらん
    return None