ALGORITHM

探索・ソートの基本

線形探索・二分探索・バブルソートを、配列を追いながら理解します。

問題を解きたい方：
→ アルゴリズム・探索トレーニングを開く

線形探索

先頭から目的の値と一致するかを1個ずつ調べます。

[18, 42, 7, 31] 42を探す 18 → 違う 42 → 発見（2回目）

整列済みの配列で中央と比較し、探索範囲を半分ずつ絞ります。

[10,20,30,40,50,60,70] 60を探す中央40 → 右半分へ中央60 → 発見

重要：二分探索では、基本的にデータがあらかじめ整列されている必要があります。

隣り合う値を比較し、昇順なら左の方が大きいときに交換します。

[5,2,4,1] 5と2 → 交換 → [2,5,4,1] 5と4 → 交換 → [2,4,5,1] 5と1 → 交換 → [2,4,1,5] 1周後、最大値5が右端へ

覚え方：
線形探索 → 先頭から順番
二分探索 → 中央から半分ずつ
バブルソート → 隣同士を比較

アルゴリズムは、問題を解決するための処理手順です。同じ結果を得る場合でも、手順によって処理時間や必要なメモリが変わるため、探索や整列などの代表的な方法を理解することが重要です。

線形探索は、データを先頭から順番に1件ずつ調べる方法です。データが整列されていなくても利用できますが、目的の値が後ろにあるほど比較回数が増えます。

二分探索は、整列済みのデータを中央で分けながら探索範囲を半分ずつ絞り込む方法です。

[2, 5, 8, 12, 17, 21, 30]から17を探すなら、まず中央の12と比較し、右半分へ絞り込みます。

線形探索は未整列でも使えます。二分探索は高速に絞り込める一方、基本的に探索対象が整列されている必要があります。

バブルソートは隣り合う要素を比較し、順序が逆なら交換する操作を繰り返す整列方法です。各回の配列状態を書き出すと処理を追いやすくなります。

読むだけで終わらない
次は実際に10問解いて、配列の動きを確認しましょう。

線形探索は先頭から順番に調べる方法で、データが整列されていなくても使えます。二分探索は整列済みのデータを半分ずつ絞り込む方法です。

[2, 5, 8, 12, 17, 21, 30] から17を探す場合、中央の12と比較します。17は12より大きいので右半分へ進み、次に21と比較します。17は21より小さいため左へ進み、17を発見できます。

隣り合う要素を比較し、順序が逆なら交換する操作を繰り返します。1回の走査で大きい値が端へ移動していく様子を追うと理解しやすくなります。

二分探索は未整列データにそのまま使えません。
「高速だから二分探索」と即決せず、データが整列されているかを最初に確認しましょう。また、配列の添字と要素の値を混同しないことも大切です。

アルゴリズム問題では、変数の値を頭の中だけで追わず、各反復後の配列・探索範囲・添字を紙に書いて追跡するとミスを減らせます。