配列の線形探索
配列の中に探している値があるかどうかは、前から 1 つずつ照らし合わせれば必ず分かります。問題はその先です。見つかったときにどう答えるか、そして最後まで無かったときに何と答えるか。この 2 つを決めないとメソッドは書けません。
見つけた瞬間にやめる
まず、見つかったあとの話です。ありがちな失敗が、答えを変数に取っておいてループが終わってから返す書き方です。
Java
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 を書くと、その場でメソッドごと終わります。
Java
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 が本物の答えとして現れることはありません。だから見つからなかったの合図に使えます。
Java
String title = "Effective Java";
System.out.println(title.indexOf("Java")); // 10
System.out.println(title.indexOf("Ruby")); // -1String の indexOf も List の indexOf も、同じ理由で -1 を返します。Java に限らず広く使われている約束なので、-1 が返ってきたら無かったと読む癖をつけてください。
やってみよう
indexOf(int[] arr, int target) は、target が最初に現れた位置を返し、無ければ -1 を返します。
- ループの中で返すのは値ではなく位置です。何を
returnするかに気をつけてください {10, 20, 30, 40}で10を探したら答えは0です。1が返るなら、数え始めを間違えています- 空の配列を渡しても落ちないはずです。ループが 1 度も回らず、そのまま最後の
returnに届きます
要件
- クラス名は
Solution、メソッド名はindexOf、引数はint[] arrとint targetの 2 つにすること - 戻り値の型は
intで、targetが見つかったら 最初に一致した位置のindexを返すこと - 見つからなかった場合は
-1を返すこと (空配列のケースも-1でよい)
入出力例
indexOf([10,20,30], 20) → 1
indexOf([10,20,30], 99) → -1
indexOf([5], 5) → 0
indexOf([10,20,30,40], 10) → 0
indexOf([10,20,30,40], 40) → 3
indexOf([10,20,10,20], 10) → 0ヒント
