配列から特定の要素を探すとき、値そのものと「インデックス（何番目か）」のどちらを取得するのが一般的ですか？

存在の有無だけを知りたい場合は真偽値を、その場所を特定して後続の処理に使いたい場合はインデックスを取得します。JavaScriptの includes や indexOf のように、言語ごとの標準メソッドを用途に合わせて使い分けるのが効率的です。

検索した値が配列の中に存在しなかった場合、プログラムが止まらないようにするにはどう書けばいいですか？

検索メソッドが「見つからない」を意味する戻り値（-1やnullなど）を返した際の処理を、if文であらかじめ記述しておきましょう。データがない場合の条件分岐を設けることで、エラーによるプログラムの停止を防ぐことができます。

配列の中に検索したい値が複数含まれている場合、すべてを抽出するにはどうすればいいですか？

最初に見つかった要素だけを返す検索メソッドではなく、filter メソッドやループ処理（for文）を活用しましょう。条件に合致するすべての要素を新しい配列に格納することで、重複するデータも漏れなく取り出すことが可能です。

配列の線形探索｜コードで実践

配列の線形探索とは

配列を先頭から順番に見ていき、目的の値があれば位置 (index) を、なければ -1 を返す線形探索アルゴリズムを書こう。

配列の線形探索

プログラミングを学んでいくと、「目的の値が配列の中に入っているか確かめたい」「入っているなら何番目かを知りたい」という場面に必ず出会います。これを実現する一番素朴で、一番大事な方法が 線形探索 (linear search) です。Java でも Python でも C でも、入門段階で必ず通る道で、List.indexOf や Array.prototype.indexOf のように標準ライブラリの中身としてもしれっと採用されています。

線形探索は「先頭から順番に 1 個ずつ見ていって、見つかったらその場で答えを返す」というだけのアルゴリズムです。発想は人間が辞書を 1 ページずつめくるのと同じで、難しい数学は何ひとつ出てきません。それでも for 文、if 文、return のすべてを総動員する、入門期の総合演習にはぴったりの題材です。

このレッスンでは、Solution.indexOf(int[] arr, int target) というメソッドを書きます。arr の中に target がいたら 最初に見つかった位置の index を返し、最後まで探してもいなかったら -1 を返す、というのが仕様です。

線形探索とは

線形探索は「とにかく前から順番に当たっていく」探索方法です。考え方は次の通りです。

配列の先頭 (index = 0) からスタートする
1 つずつ要素を target と比較する
同じ値を見つけたら、その時点の index を return してすぐ終わる
最後まで見つからなければ -1 を返す

たとえば arr = [10, 20, 30, 40, 50]、target = 30 のときは、index = 0 の 10 を見て違う、index = 1 の 20 を見て違う、index = 2 の 30 を見つけた、で 2 を返します。target = 99 だったら、最後まで見ても一致せず -1 を返します。

アルゴリズムの世界では、これに対して 二分探索 (binary search) というもっと速い手法もあります。ただし二分探索は「配列が小さい順に並んでいる」という前提が必要です。並んでいない配列に対しては、線形探索が一番素直で確実な選び方になります。

Java の文法を確認する

線形探索を書くには、次の Java の道具を組み合わせます。

配列の長さを得る arr.length (関数ではなくフィールドなので () は付けない)
配列の i 番目の要素にアクセスする arr[i]
等しいかを比べる == (int などプリミティブ型は == で OK)
ループの途中で関数を抜ける return

コードの骨格は、次のとおりです。

Java

public class Solution {
    public static int indexOf(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }
}

たった 7 行ですが、線形探索のエッセンスが詰まっています。読み下すと「i を 0 から arr.length - 1 まで動かす。途中で arr[i] == target ならその場で i を返す。最後まで通ったら -1 を返す」となります。

ループの中で return を書くと、その瞬間にメソッドごと終わります。break は「ループだけ抜ける」、return は「メソッドごと抜ける」と覚えると、使い分けが頭に入りやすいです。線形探索では、見つけた瞬間に値を返したいので return が一番素直です。

探索フローを図で確認する

arr = [10, 20, 30, 40, 50] で target = 30 を探したとき、ループの中で何が起きるかをフローチャートで追ってみましょう。

diagram (will load when visible)

ループの開始時に i < arr.length を確認し、配列の範囲を超えていれば -1 を返してメソッド終了です。範囲内なら arr[i] と target を比べ、一致していれば i を返して終了、違っていれば i を 1 進めて先頭の判定に戻る、という流れになります。

図を見るとわかるように、見つかった場合と見つからなかった場合で 出口が 2 つ あります。return i; で抜けるルートと、ループを抜けてから return -1; で抜けるルート、この 2 本立てが線形探索の特徴です。

計算量 O(n) の話

線形探索の処理時間は、配列の長さ n に比例します。最悪のケース、つまり target が配列の末尾にあるか、そもそも存在しない場合は、要素を n 個すべて見比べることになります。これを 計算量 O(n) (オーダー・エヌ) と呼びます。O は order の頭文字で、「だいたいこの程度のステップ数で済む」という指標です。

n = 10 の配列なら、最悪 10 回の比較
n = 1000 なら、最悪 1000 回
n = 1000000 なら、最悪 1000000 回

同じ「探す」処理でも、二分探索なら O(log n) で、n = 1000000 でも 20 回程度の比較で終わります。アルゴリズムの選び方ひとつで、計算量が圧倒的に変わるという感覚は、これから Java でも Python でもずっと付いて回るテーマです。今は「線形探索は配列の長さに比例して時間がかかる」とだけ覚えておけば十分です。

別解 ─ 拡張 for で書いてみる

もうひとつ、Java には 拡張 for 文 (for-each) という記法があります。配列の中身を頭から順に取り出すループで、添字 i を自分で管理しなくて済む、という便利な書き方です。

Java

public class Solution {
    public static int indexOf(int[] arr, int target) {
        int index = 0;
        for (int value : arr) {
            if (value == target) {
                return index;
            }
            index++;
        }
        return -1;
    }
}

for (int value : arr) は「arr の要素を value という名前で 1 個ずつ取り出す」という書き方です。ただし、拡張 for では「今何番目か」を直接知る方法がないので、int index = 0; の変数を別に用意して、ループの最後で index++ してあげる必要があります。

どちらの書き方が良いかは好みによりますが、「位置を知りたい」場面では普通の for (int i = 0; i < arr.length; i++) のほうが素直です。逆に「位置はどうでもよくて、合計や最大値だけ知りたい」場面では、拡張 for のほうがすっきり書けます。

よくある間違い

線形探索を初めて書くと、次の 3 つの落とし穴のどれかにハマる人がとても多いです。

見つかった後もループを続けてしまう — for の中で return i; ではなく、int found = i; のように変数に保存するだけにしてしまうと、後ろにある同じ値で found が上書きされてしまうことがあります。「先頭から見て最初に見つかった位置」という仕様なので、見つけた瞬間に return で抜けるのが正解です。どうしてもループの後で返したい場合は、見つかった時点で break; してから return found; する形にしましょう
index の初期化忘れ / 初期化ミス — 拡張 for で書くときに int index = 0; の宣言を忘れると cannot find symbol のコンパイルエラーになります。逆に int index = -1; から始めてしまうと、arr[0] が target と一致したときに -1 が返ってしまい、テストが fail します。初期値は 0 が正解です
複数一致の挙動を取り違える — arr = [10, 20, 10, 20] で target = 10 の答えは、0 (最初の 10) であって 2 (後ろの 10) ではありません。普通の for ループで先頭から return する書き方になっていれば自然に 0 が返りますが、「最後に一致した index を返したい」と仕様を勘違いすると 2 を返すコードを書いてしまいます。仕様を読むときに「最初」「最後」「全部」のどれを期待されているか必ず確認するクセを付けましょう

もうひとつ細かい話として、arr が空配列 (length = 0) のケースもよくあります。今回の for (int i = 0; i < arr.length; i++) の書き方なら、arr.length が 0 のときは最初から i < 0 が false になり、ループに一度も入らずに return -1; まで素通りします。空配列にも自然に対応できているのが、シンプルな線形探索の良いところです。

エッジケース (空配列、要素 1 個、target が先頭、target が末尾) を頭の中で 1 ケースずつ走らせるクセをつけると、バグが入りにくいコードが書けるようになります。テストは「想定外を発見する装置」ではなく、「自分の仮説を確かめる装置」だと思って書きましょう。

やってみよう

それでは右側のエディタで、Solution.indexOf(int[] arr, int target) メソッドを完成させましょう。手順は次のとおりです。

for (int i = 0; i < arr.length; i++) のループを書く
ループの中で if (arr[i] == target) を判定する
条件が成立したら return i; でメソッドを抜ける
ループを抜けたら return -1; を書く
「実行」ボタンを押して、すべてのテストが緑になることを確認する

動いたら、ぜひ拡張 for 文バージョンに書き換えてみたり、if の条件を > や < に変えて「target より大きい最初の要素の位置」を返す関数に改造してみてください。同じループ構造で、判定だけ差し替えれば、さまざまな探索メソッドに早変わりします。

線形探索は、配列を扱うあらゆる場面で土台になる考え方です。「先頭から順に見て、条件に合ったらすぐ返す」というパターンを体に染み込ませておけば、合計の計算、最大値の探索、特定条件のフィルタリングと、応用先がどんどん広がっていきます。ここでしっかり手を動かしておきましょう。

次のレッスン

次は 拡張 for ループ で、配列を先頭から順番に見ていき、目的の値があれば位置 (index) を、なければ -1 を返す線形探索アルゴリズムを書こうを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

線形探索の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 線形探索とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

配列の線形探索

配列の線形探索

線形探索とは

Java の文法を確認する

探索フローを図で確認する

計算量 O(n) の話

別解 ─ 拡張 for で書いてみる

よくある間違い

やってみよう

次のレッスン

要件

入出力例

ヒント

参考リンク

メモ