12　標準アルゴリズム（線形探索・最大値・最小値）

「知っている人には当たり前」のアルゴリズムを、自分で書けるようにする。

これまでに学んだ変数・繰り返し・条件分岐・配列・関数を組み合わせると、 実務でよく使う処理が実現できます。 この資料ではその基本中の基本——探索・最大値・最小値を扱います。

試験ではこれらのアルゴリズムのコードを読んで動作を追う問題、 あるいは空欄を埋める問題が頻出します。 コードのパターンを体に染み込ませましょう。
この資料のプログラムでは、配列の要素番号は1から始まるものとします。

1. 線形探索（リニアサーチ）

配列の要素を先頭から順番に1つずつ調べ、目的の値を探す最もシンプルな探索方法です。

コード：見つかれば true を返す

○論理型: linear_search(整数型の配列: array, 整数型: key)
    整数型: i
    論理型: found ← false

    for ( i を 1 から array の要素数 まで 1 ずつ増やす )
        if ( array[i] が key と等しい )
            found ← true
        endif
    endfor

    return found

コード：見つかった位置（要素番号）を返す

○整数型: linear_search_idx(整数型の配列: array, 整数型: key)
    整数型: i

    for ( i を 1 から array の要素数 まで 1 ずつ増やす )
        if ( array[i] が key と等しい )
            return i       // 見つかった時点で返す（以降は処理しない）
        endif
    endfor

    return -1              // 見つからなかった場合

動作の流れ（array = {4, 7, 1, 5, 9}、key = 5 の場合）

[1] 4 [2] 7 [3] 1 [4] ★ 5 [5] 9 i=1 4≠5 i=2 7≠5 i=3 1≠5 i=4 5=5 ✓ 発見！ → true を返す / 要素番号 4 を返す key が見つからなかった場合：全要素を調べ終えても一致なし → false / -1 を返す
return i の意味：return に到達した時点で関数はその場で終了します。 「見つかったら即座に返す」ため、残りの要素を無駄に調べません。 見つからなかった場合のみ for ループが最後まで回り、return -1 に到達します。

2. 最大値の探索

配列の先頭要素を「暫定の最大値」として持ち、残りの要素と順に比較しながら更新していきます。 

○整数型: find_max(整数型の配列: scores)
    整数型: i
    整数型: max ← scores[1]   // 最初の要素で初期化

    for ( i を 2 から scores の要素数 まで 1 ずつ増やす )
        if ( scores[i] が max より大きい )
            max ← scores[i]   // より大きければ更新
        endif
    endfor

    return max

動作の流れ（scores = {45, 72, 68, 91, 53} の場合）

ステップ 比較 結果 max の値 初期化 max ← scores[1] = 45 比較なし 45 i=2 72 > 45? Yes → 更新 72 i=3 68 > 72? No → 変化なし 72 i=4 91 > 72? Yes → 更新 91

i=5 で 53 > 91? → No → 変化なし。最終的に max = 91 が返される。

3. 最小値の探索

最大値とほぼ同じ構造で、比較演算子を「より大きい」から「より小さい」に変えるだけです。

○整数型: find_min(整数型の配列: values)
    整数型: i
    整数型: min ← values[1]   // 最初の要素で初期化

    for ( i を 2 から values の要素数 まで 1 ずつ増やす )
        if ( values[i] が min より小さい )
            min ← values[i]   // より小さければ更新
        endif
    endfor

    return min
初期化は必ず配列の先頭要素で行います。
0 や 999 のような定数で初期化すると、データによっては正しい結果が得られません。 「配列の中から探す」のだから、初期値も配列の中の値であるべきです。

4. 3つのアルゴリズムの比較

アルゴリズム目的初期化更新条件戻り値
線形探索（true/false）値が存在するかfound ← false一致したら true論理型
線形探索（位置）値の位置なし一致したら return i整数型（-1は未発見）
最大値探索最も大きい値max ← array[1]array[i] > max のとき整数型
最小値探索最も小さい値min ← array[1]array[i] < min のとき整数型

5. 理解度チェック問題

問題12-1

次の関数を linear_search({3, 6, 9, 12, 15}, 10) として呼び出したとき、戻り値はどれか。

○論理型: linear_search(整数型の配列: array, 整数型: key)
    整数型: i
    論理型: found ← false
    for ( i を 1 から array の要素数 まで 1 ずつ増やす )
        if ( array[i] が key と等しい )
            found ← true
        endif
    endfor
    return found
解説を表示 正解：イ
10 は配列 {3, 6, 9, 12, 15} の中に存在しないため、found は true に更新されず false のまま返ります。

問題12-2

次の関数を find_max({18, 24, 21, 30, 27}) として呼び出したとき、戻り値はどれか。

○整数型: find_max(整数型の配列: scores)
    整数型: i
    整数型: max ← scores[1]
    for ( i を 2 から scores の要素数 まで 1 ずつ増やす )
        if ( scores[i] が max より大きい )
            max ← scores[i]
        endif
    endfor
    return max
解説を表示 正解：ウ
max は 18 → 24 → 30 と更新されます。最終的な最大値は 30。

問題12-3　空欄補充

次の関数の最小値探索で、空欄 ［ A ］ に入るものを選びなさい。

○整数型: find_min(整数型の配列: data)
    整数型: i
    整数型: min ← ［ A ］
    for ( i を 2 から data の要素数 まで 1 ずつ増やす )
        if ( data[i] が min より小さい )
            min ← data[i]
        endif
    endfor
    return min
解説を表示 正解：エ
最初の要素 data[1] で初期化し、2番目以降と比較するのが正しいパターンです。
0 や 999 は「データの値の範囲がわからない」場合に誤動作の原因になります。

問題12-4　空欄補充

次の関数は配列から key を探し、最初に見つかった要素番号を返す。見つからなければ -1 を返す。空欄 ［ B ］ に入るものを選びなさい。

○整数型: linear_search_idx(整数型の配列: a, 整数型: key)
    整数型: i
    for ( i を 1 から a の要素数 まで 1 ずつ増やす )
        if ( a[i] が key と等しい )
            ［ B ］
        endif
    endfor
    return -1
解説を表示 正解：ア
見つかった時点で要素番号 i を返します。return に到達するとそこで関数が終了するため、 見つかった場合は残りの要素を調べません。見つからなかった場合のみ最後の return -1 に到達します。

問題12-5

次のコードを実行すると result の値はいくつになるか。

整数型の配列: nums ← {12, 4, 9, 6, 15}
整数型: i
整数型: min ← nums[1]

for ( i を 2 から nums の要素数 まで 1 ずつ増やす )
    if ( nums[i] が min より小さい )
        min ← nums[i]
    endif
endfor

整数型: result ← min
解説を表示 正解：ウ
min は 12 → 4（i=2 で更新）→ その後 9, 6, 15 はいずれも 4 より大きいので更新なし。最小値は 4。