番兵あり・なしの違いをその場で見比べる
同じ配列と探索値で、通常の線形探索と番兵法の判定回数の差をその場で比較できます。
自動実行の速度
420 ms
未発見時は番兵で停止
番兵なし
準備完了
各ステップで index < length を確認し、そのあとで配列の要素と探索値を比較します。
- 現在位置(index)
- 0
- 結果
- 探索中
- 要素比較
- 0
- 範囲確認
- 0
- 合計判定
- 0
- 探索値
- 14
擬似コード
int search(int array[], int target, int length) {
int index;
/* 線形探索 */
for (index = 0; index < length; index++) {
if (array[index] == target) {
break;
}
}
return index;
}
判定は各反復で `index < length` と `array[index] == target` を見ます。後ろまで調べるほど判定回数が増えます。
番兵あり
準備完了ループ中は範囲確認せず、要素比較だけで進みます。止まったあとに、元の配列内かを 1 回だけ確認します。
- 現在位置(index)
- 0
- 結果
- 探索中
- 要素比較
- 0
- 最後の確認
- 0
- 合計判定
- 0
- 探索値
- 14
擬似コード
int search(int array[], int x, int num) {
int i;
/* ダミーのデータを格納 */
array[num] = x;
/* 線形探索 */
i = 0;
while (1) {
if (array[i] == x) {
break;
}
i++;
}
return i;
}
/* 呼び出し側で判定 */
if (search(array, x, num) < num) {
/* 発見 */
} else {
/* 番兵で停止 = 未発見 */
}
`while` の中では `array[i] == x` だけを見ます。
止まったあとに、下の `if (search(array, x, num) < num)` が 1 回だけ本物か番兵かを判定する部分です。
止まったあとに、下の `if (search(array, x, num) < num)` が 1 回だけ本物か番兵かを判定する部分です。
比較まとめ
番兵なしの合計判定
0
番兵ありの合計判定
0
削減できた判定数
0
まずは「1ステップ」か「自動実行」で探索を進めてください。
見つからないケースや末尾で見つかるケースにすると、番兵の差が見えやすくなります。
ステップログ
番兵なし
番兵あり