| English | 意味 |
|---|---|
| traversal/træˈvɜːsl/ | トラバース |
| index/ˈɪndeks/ | インデックス |
| linear search/ˈlɪnɪə sɜːtʃ/ | 線形探索 |
標準的な配列アルゴリズム
- ほとんどの配列タスクは、走査に数ある標準パターン中的一个 を加えたものです。
- 合計 / 平均: 総計を蓄積し、
lengthで割ります。 - カウント: 要素が条件に一致したら増分します。
- 最小 / 最大: これまでに見た最小値または最大値を追跡します。
最大値の探索
max = a[0](最初の要素) で始め、インデックス1から走査します。- ループ内で
if (a[i] > max) { max = a[i]; }を更新します。 - ループ後、
maxには配列内の最大値が入っています。 - 最初の要素から始め、
0からはじめないでください —0はすべての値より大きい可能性があります。
値の検索
- 値が存在するか確認するには、走査して各要素を比較します。
- 見つけた場所のインデックスを返すか、ループが一致なく終了した場合は
-1を返します。 - ループ内では
if (a[i] == target) return i;、その後はreturn -1;。 - これは線形探索です (Unit 4.14 で詳細を扱います)。
シフトと変更
- いくつかのアルゴリズムは要素を移動または変更します — 例: すべて左にシフト、または各値を倍増。
- 変更にはインデックス付きループが必要で、
a[i] = ...に割り当てることができます。 - ⟨
a[i+1]⟩ の読み出し時の境界に注意 — 最後のインデックスには隣接要素がありません。 - 境界外アクセスを避けるためにインデックスを慎重にトレースします。
max/min探索は、0ではなく最初元素から初期化してください。 int max = 0;はすべての値が負数の場合に失敗し（0と誤って報告します）、int max = a[0];を使用しループをインデックス1から始めます。また、アルゴリズムがa[i+1]を読む場合、ループをi < a.length - 1で停止しないと最終反復で先読みしてしまいます。
a の最大値を見つける:
int max = a[0];for (int i = 1; i < a.length; i++) { if (a[i] > max) max = a[i]; }- For
a = {3, 9, 5}: max は9になります。
配列アルゴリズムは走査とパターンの組み合わせです: 合計/平均、カウント、min/max、または検索 (インデックスまたは -1 を返す)。min/max を 0 ではなく最初の要素で初期化します。要素の変更にはインデックス付きループが必要で、a[i+1] の読み出しには範囲内に留めるために厳密な境界が必要です。
最大値を見つける
max は a[0]=3 から始まり、9 に変わり、その後変化せず（a = {3,9,5}）。
配列の最大値を見つけるには、max を以下のように初期化する必要があります...
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
0から始めると、すべての値が負の場合に失敗します。
For a = {3, 9, 5}, 最大値は何ですか？
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
9 が最大の要素です。
線形探索でターゲットが見つからない場合、何を返しますか？
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
慣例として、-1 は「見つからない」を意味します。
a[i+1] を読むアルゴリズムでは、ループを以下のように停止すべきです...
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
1つ早く停止することで a[i+1] が境界内に収まります。
配列の要素を修正（a[i] = ...）するには、for-each ではなくインデックス付きループが必要です。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
for-each は配列への再代入ができないためです。