何を返す処理なのか、最初に決める
a={4,7,4}でtarget=4を探すと、1番目で一致するので1を返します。配列の中の値4を返す問いではありません。
また、この例は最初の一致で終了するので、後の3番目まで探して置き換える処理でもありません。探索の目的が最初の位置なのか全ての位置なのかで処理は変わります。
関数の入力、返す値、停止条件を問題の前提から整理します。
| target | 返す番号 | 値の比較回数 |
|---|---|---|
| 4 | 1（最初の一致） | 1回 |
| 7 | 2 | 2回 |
| 9 | 0（未発見） | 3回 |
| 空配列で4 | 0（未発見） | 0回 |
比較した要素だけを数える
target=7なら、最初の4と7は不一致、次の7と7が一致するので、値の比較は2回です。target=9なら3要素すべてが不一致で3回。
ここで数えるのはa[i]とtargetの値の等しさの比較です。ループを続ける条件の確認、代入、返却などの操作をすべて同じ比較回数として足しません。
何を一回と数えるかを明示します。
未発見と空の配列を、別の条件として追う
全要素が不一致なら0を返します。0は今回の要素番号1からの例で、有効な番号と区別できる未発見の値として定義したものです。
全ての探索が0を返す規則ではありません。空の配列は最初から要素がないため、値の比較は0回で未発見となります。
線形探索は整列済みであることを前提にしませんが、二分探索など別の方法の前提へそのまま広げません。本単元はこの順次探索の追跡に範囲を絞ります。