問題の分解と基本アルゴリズム・境界値対応

問題を手順に分解する

複雑に見える問題でも、小さな手順に分解すると見通しが良くなります。例えば「ある数がリストの中にあるかどうかを調べる」という問題は、次のように分解できます。

1. リストの先頭から順番に要素を見ていく
2. 探している値と一致する要素が見つかったら、その位置を記録して終了する
3. 最後まで見つからなければ、「見つからなかった」ことを表す結果を返す

この手順をそのままコードにしたものが「線形探索（linear search）」です。

線形探索

fn linear_search(numbers: &Vec<i32>, target: i32) -> Option<usize> {
    for (index, &value) in numbers.iter().enumerate() {
        if value == target {
            return Some(index);
        }
    }
    None
}

fn main() {
    let numbers = vec![10, 20, 30, 40, 50];

    match linear_search(&numbers, 30) {
        Some(index) => println!("見つかりました（添字: {}）", index),
        None => println!("見つかりませんでした"),
    }
}

• numbers.iter().enumerate()で、「添字」と「値」の両方を同時に取り出せます。
• 見つかったらその場でSome(index)を返して処理を終えます（これを「早期リターン」と呼びます）。
• 最後まで見つからなければループを抜けてNoneを返します。

どんな問題に使うか

線形探索は、「データが並んでいる順番に特別な規則がない」場合に使える最も基本的な探索方法です。データが整列（ソート）されている場合は、より高速な「二分探索」を使うことができますが、これはIntermediate以降で扱います。

計算量

• 時間計算量：O(n) — 最悪の場合、n個すべての要素を1回ずつ調べる必要があります。
• 空間計算量：O(1) — 探索のために新しく確保するメモリは、要素数によらず一定です。

境界値への配慮

アルゴリズムを実装するときは、次のような境界条件を忘れずに確認しましょう。

• リストの要素数が0個のとき
• 探している値がリストの先頭／末尾にあるとき
• 探している値が複数回出現するとき（最初に見つかったものだけを返すのか、すべて返すのか）

演習：線形探索