2011-12-03 13 views
0

強化されたバージョン:主な違い - 逐次探索アルゴリズム

A[n] <-- K 
i <-- 0 

while A[i] != K do 
    i <-- i + 1 

if i<n 
    return i 
else 
    return -1 

ノーマルバージョン

i <-- 0 

while i <n and A[i] != K do 
    i <-- i + 1 

if i<n 
    return i 
else 
    return -1 

強化版と通常版との主な違いは何ですか?ポイントは何ですか?

答えて

4

後者は、各繰り返しで1つの余分な比較(i < n)を実行する点が異なります。

+2

拡張された手法は、ターゲット配列の最後にセンチニアル値(Kのコピー)を配置します(これに対して余分な位置が存在すると仮定します)。このアルゴリズムは、単一のループ比較操作で終了してKを見つけることが保証されています。 Kがi = Nより前に見つかると、それは配列内にあり、そうでない場合は配列内にあります。 – bjg

関連する問題