いろんなアルゴリズム"00.00.00.11"

立ち位置・仕様

• いろんなアルゴリズムをコピペできるように記録するのみ
• 最適化が目的でない
• たまにメモとして解説を残す
• 最低限でまとめる
• データを抽出しやすいように個別のIDを付与
• あるアルゴリズムにおいて、他のアルゴリズムが登場する際にはそのIDを付与
• IDは16進数表記
• なるべく最低限なパッケージで実装
• なるべく特殊なオブジェクト型は使用しない

TargetID

00.00.00.11

ReferenceID

センチネルによる線形探索（sentinel linear search）

• 最後の一要素分だけ探索しなくて良いので，線形探索より微小だが速くなる

def sentinelLinearSearch(l, x):
    n = len(l)
    last = l[n - 1]
    l[n - 1] = x
    
    i = 0
    while (l[i] != x):
        i += 1

    l[n - 1] = last
    if ((i < n - 1) or (l[n - 1] == x)):
        return i
    else:
        return -1

使用方法

l = [2,6,1,8,10,7,3,5]
print(sentinelLinearSearch(l, 8)) # 3