| English | 意味 |
|---|---|
| Searching/ˈsɜːtʃɪŋ/ | 探索 |
| linear search/ˈlɪnɪə sɜːtʃ/ | 線形探索 |
| binary search/ˈbaɪnəri sɜːtʃ/ | 二分探索 |
| sorted/ˈsɔːtɪd/ | ソート済み |
値の探索
- 検索 とは、コレクションからターゲット値の位置を特定することです。
- 2つの標準アルゴリズム: 線形検索 と 二項検索。
- どちらもターゲットが存在する インデックス を返すか、または「未発見」信号（通常は
-1）を返します。 - どちらを使用するかは、データが ソート済み かどうかによります。
線形探索（Linear Search）
- 先頭から各要素を 1つずつ確認 し、ターゲットが見つかるまで続けます。
for (int i = 0; i < a.length; i++) if (a[i] == target) return i;- ソート済みでも未ソートでも どの配列でも機能します。
- 最悪ケース: すべての 要素を確認します（
n回のチェック）。
二項探索（Binary Search）
- ソート済み の配列が必要です。毎回 中央 の要素を確認します。
- 中央がターゲットなら完了。ターゲットが 小さい 場合は 左半分 を検索し、大きい 場合は 右半分 を検索します。
- ステップごとに残りの検索範囲が 半減 します。
- 大きな整列済み配列に対して非常に高速です。約
log₂ n回のチェックで済み、n回のような全探索とは異なります。
二項検索が速い理由
- 百万個のアイテムの線形探索：最大で百万回のチェックが必要です。
- 百万個の整列済みアイテムの二分探索：約20回のチェックで済みます。
- 注意点: 配列が 既にソート済み である必要があります。
- 繰り返し半減させることが
O(log n)の核心アイデアです。
二項検索は SORTED（ソート済み）な配列でのみ機能し、未ソートデータで実行すると結果が誤りになります。 また、ステップ毎に 中央 と比較して範囲の 半分 を除外しますが、線形検索は 先頭 から比較して 1つ の要素だけを除外します。データがソート済みかどうか不明な場合は、線形検索を使用するか、事前にソートする必要があります。
[1, 3, 5, 7, 9] 内の7に対する二項検索:
- 中央は
5(インデックス2)。 7 > 5 なので、右半分を検索。 - 右半分は
[7, 9]；中央は7。インデックス3で見つかりました。 - 4回ではなく2回のチェック — 毎回範囲が半減しました。
線形検索 は先頭から要素をチェックします（どの配列でも機能し、最大 n 回のチェック）。二項検索 は ソート済み 配列が必要で、中央 と比較して各ステップで検索範囲を 半減 します（約 log₂ n 回のチェック）。どちらも見つけたインデックス、または -1 のような「未発見」信号を返します。
線形探索と二項探索
二項探索は各ステップで整列された範囲を半分にします。
線形探索は...
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
線形探索 = 先頭から末尾まで；あらゆる配列で動作する。
二項探索には配列が...であることが必要。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
二項探索は整列されたデータのみで動作する。
二項探索の各ステップで...
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
中央と比較して片方の半分を維持する。
[1,3,5,7,9] で 7 を二項探索する場合：何回の比較が必要か（毎回中央）？
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
5 と比較し、次に 7 と比較 — 2回の比較。
二項探索は未整列の配列でも正しい結果を与える。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
順序に依存するため、未整列のデータでは破綻する。
各探索とその性質を対応させよ。
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
線形探索は汎用的だが遅く、二項探索は速いが順序を必要とする。