線形探索 sequential search
2020-08-31
こんにちは、0371です。
今回は、配列の中から任意の値が格納されている添字を導き出す方法について書いていきます。
基本情報技術者試験のアルゴリズムの問題集から、擬似言語の問題を実際の言語でプログラミングしてみました。
コード
今回も、ArrayListを使用して、配列の中から任意の値が格納されている添字を求めます。
言語はJavaです。
main関数内の変数 answerに0~9までの好きな数値を当てはめてください。
任意の値が見つかったら探索を終了するプログラム
Main.java
import java.util.ArrayList;
import java.util.Random;
public class Main {
public static void main(String[] args) {
int listsize = 10;
int range = 10;
int answer = 8; // ここに0~9までの好きな数値を入れる
ArrayList<Integer> list = new ArrayList<>();
Random rand = new Random();
for(int i=0; i<listsize; i++)list.add(rand.nextInt(range));
System.out.println(list);
seqSearch(list, answer);
}
private static void seqSearch(ArrayList<Integer> list, int answer) {
int pos = -1;
for(int k = 0; k < list.size() && pos == -1; k++) {
if(list.get(k) == answer) {
pos = k;
System.out.println(answer+"は、添字の["+pos+"]に格納されています。");
}
}
if(pos == -1)System.out.println(answer+"は、格納されていませんでした。");
}
}
Random()とnextInt();を使用することによって、実行するたびに1~9までのランダムなint型の数値を配列の中身へ代入しています。
seqSearch()のforループの中で、添字の0番目から順番にanswerと値が一致するかを比較していきます。
一致した場合、posに値を代入し、answerがpos番目の添字に格納されていることを表示します。
また、一致する値がない場合は、格納されていないことを表示しています。
何度か実行した結果は以下の通りです。
[7, 1, 9, 9, 8, 9, 4, 4, 7, 1]
8は、添字の[4]に格納されています。
[4, 8, 2, 0, 9, 8, 7, 4, 7, 6]
8は、添字の[1]に格納されています。
[2, 6, 6, 1, 4, 7, 3, 3, 3, 5]
8は、格納されていませんでした。
実行結果の二番目を見ていただけるとわかると思うのですが、添字の[5]番目にもanswerが格納されています。
しかし、探索結果には出てきていません。
これは、上記のプログラムでは配列内にanswerが複数ある場合でも、1つ目を見つけた時点で探索を終了してしまうためです。
配列の最後の添字に到達するまでは、探索を続行するプログラム
これを避けるためには、seqSearch()のforループの条件を書き換えます。
&& pos == -1を削除しましょう。
=== 省略 ===
private static void seqSearch(ArrayList<Integer> list, int answer) {
int pos = -1;
for(int k = 0; k < list.size(); k++) {
if(list.get(k) == answer) {
pos = k;
System.out.println(answer+"は、添字の["+pos+"]に格納されています。");
}
}
if(pos == -1)System.out.println(answer +"は、格納されていませんでした。");
}
=== 省略 ===
これで、配列内のanswer全てを探索することができます。
実行結果を見てみましょう。
[7, 2, 9, 4, 1, 8, 7, 2, 1, 8]
8は、添字の[5]に格納されています。
8は、添字の[9]に格納されています。
成功ですね。
複数の任意の値を探索するプログラム
また、複数のanswerを探索する場合は下記のようなコードになります。
answerListを作成し、二重ループで探索します。
answerListのn個目の探索が終了する時にposを-1に初期化しているところがポイントです。
また、boolean notFoundで、answerListから一つも見つからなかった場合には、answerListの配列の中身を表示させて、「格納されていませんでした。」と最後に表示させるようにしています。
二重ループを構成する時は、ループのための変数が区別しやすくなるような命名をしましょう。
可読性が高まるので、とてもおすすめです。
このプログラムでいうと、iはlis_i、kはans_kとしています。
import java.util.ArrayList;
import java.util.Random;
public class Main {
public static void main(String[] args) {
int listsize = 10;
int range = 10;
ArrayList<Integer> list = new ArrayList<>();
Random rand = new Random();
for(int i=0; i<listsize; i++)list.add(rand.nextInt(range));
System.out.println(list);
ArrayList<Integer> answerList = new ArrayList<>();
// answerList.add(); は増やしても良い
answerList.add(3); // ここに0~9までの好きな数値を入れる
answerList.add(4); // ここに0~9までの好きな数値を入れる
seqSearch(list, answerList);
}
private static void seqSearch(ArrayList<Integer> list, ArrayList<Integer> answerList) {
int pos = -1;
boolean notFound = true;
for(int ans_k = 0; ans_k < answerList.size(); ans_k++) {
System.out.println();
System.out.println(answerList.get(ans_k)+" の添字番号を探索します。");
for (int lis_i = 0; lis_i < list.size(); lis_i++) {
if(list.get(lis_i) == answerList.get(ans_k)) {
pos = lis_i;
System.out.println(answerList.get(ans_k)+"は、添字の["+pos+"]に格納されています。");
notFound = false;
}
}
if(pos == -1)System.out.println(answerList.get(ans_k) +"は、格納されていませんでした。");
pos = -1;
}
if(notFound) {
System.out.println();
System.out.println(answerList +"は、格納されていませんでした。");
}
}
}
何度か実行してみます。
[5, 3, 9, 0, 9, 5, 9, 3, 0, 8]
3 の添字番号を探索します。
3は、添字の[1]に格納されています。
3は、添字の[7]に格納されています。
4 の添字番号を探索します。
4は、格納されていませんでした。
[1, 4, 2, 2, 8, 3, 7, 7, 4, 7]
3 の添字番号を探索します。
3は、添字の[5]に格納されています。
4 の添字番号を探索します。
4は、添字の[1]に格納されています。
4は、添字の[8]に格納されています。
[9, 9, 6, 7, 0, 8, 2, 7, 1, 1]
3 の添字番号を探索します。
3は、格納されていませんでした。
4 の添字番号を探索します。
4は、格納されていませんでした。
[3, 4]は、格納されていませんでした。
成功していますね。
今日の一言
線形探索は初歩的な探索方法なので、しっかり覚えたい。