配列の線形探索

配列の中に探している値があるかどうかは、前から 1 つずつ照らし合わせれば必ず分かります。問題はその先です。見つかったときにどう答えるか、そして最後まで無かったときに何と答えるか。この 2 つを決めないとメソッドは書けません。

見つけた瞬間にやめる

まず、見つかったあとの話です。ありがちな失敗が、答えを変数に取っておいてループが終わってから返す書き方です。

int[] balances = {120, 45, -30, -80};
int firstMinus = 0;
for (int i = 0; i < balances.length; i++) {
    if (balances[i] < 0) {
        firstMinus = balances[i];
    }
}
System.out.println(firstMinus); // -80。欲しかったのは -30

最初にマイナスになった月の残高を知りたいのに、返ってきたのは -80 です。条件に合う要素が 2 つあり、あとから来たほうが firstMinus を上書きしてしまいました。

欲しいのは最初の 1 件なので、見つけた時点でもう先を見る必要がありません。ループの中に return を書くと、その場でメソッドごと終わります。

for (int i = 0; i < balances.length; i++) {
    if (balances[i] < 0) {
        return balances[i]; // ここで終わり。残りは見ない
    }
}

break と混同しやすいので整理しておきます。break はループから抜けるだけでメソッドの続きは実行され、return はメソッドごと終わります。最初の 1 件が分かれば用が済む探索では、return のほうが素直です。

無かったときに返す値を決める

次に、最後まで見ても見つからなかった場合です。ループを抜けた先にも return を 1 つ置かないと、そもそもコンパイルが通りません。戻り値が int のメソッドは、どの道を通っても必ず値を返す必要があるからです。

そこで何を返すかは自分で決めます。上の例では 0 にしましたが、これは危うい選択です。残高が本当に 0 円の月があったら、見つからなかったのか 0 円だったのかを、呼び出した側が区別できません。

見つからなかったことを表す専用の値を 番兵 と呼びます。良い番兵は、本物の答えとして絶対に出てこない値です。

位置を答えるなら -1

今回の課題で返すのは、値そのものではなく何番目にあったかです。添字は 0 1 2 と 0 以上の整数しか取らないので、-1 が本物の答えとして現れることはありません。だから見つからなかったの合図に使えます。

String title = "Effective Java";
System.out.println(title.indexOf("Java")); // 10
System.out.println(title.indexOf("Ruby")); // -1

String の indexOf も List の indexOf も、同じ理由で -1 を返します。Java に限らず広く使われている約束なので、-1 が返ってきたら無かったと読む癖をつけてください。

やってみよう

indexOf(int[] arr, int target) は、target が最初に現れた位置を返し、無ければ -1 を返します。

• ループの中で返すのは値ではなく位置です。何を return するかに気をつけてください
• {10, 20, 30, 40} で 10 を探したら答えは 0 です。1 が返るなら、数え始めを間違えています
• 空の配列を渡しても落ちないはずです。ループが 1 度も回らず、そのまま最後の return に届きます

1. クラス名は Solution、メソッド名は indexOf、引数は int[] arr と int target の 2 つにすること
2. 戻り値の型は int で、target が見つかったら 最初に一致した位置の index を返すこと
3. 見つからなかった場合は -1 を返すこと (空配列のケースも -1 でよい)