【アルゴリズム】線形探索(番兵法)|基本情報技術者 科目B対策

 

2023年4月から基本情報技術者の試験制度が変更されたものの科目B(旧:午後問題)の重要さは変わりません。

出題方式は「多肢選択式」で以前と同じですが、データ構造及びアルゴリズムが8割、情報セキュリティが2割の割合で出題される点が大きく変わっています。

合格基準点は600点以上/1000点満点中、つまり6割以上取れれば合格になります。

そんな科目Bのデータ構造及びアルゴリズムについて、基本となる探索の問題について考えてみましょう。

 

 

目次

 

 

探索アルゴリズムとは??

配列のようなデータの集合から目的の値をを持った要素を探し出すアルゴリズムのことを言います。

何らかの項目(属性)に着目して探索を行います。このとき、着目する項目を「キー」と呼びます。例えば、年齢に着目して探索を行う場合、キーは年齢ということになります。

 

<探索アルゴリズム例>

・線形探索

・2分探索

・ハッシュ法  等

 

 

線形探索とは??

線形探索は、「配列からの探索手法としてもっとも基本的なアルゴリズム」です。

直線上に並んだ要素(配列)からの探索は、目的とする値を持つ要素が見つかるまで先頭から順に要素を探していくことで実現します。

番兵法はこのコストを半分に抑えます。データの最後尾に目的とする値を格納するという前準備を行うことで2度if文を利用していたところを1回の利用で済むようになります。

 

例えば、配列を探索する手順は下記のようになる。

1.1番目の要素である値に着目し、目的の値であるか比較・確認を行います。

  目的の値であった場合、データの最後尾に設定した値であるかを確認後、

  目的の値であれば、探索は成功で処理は終了です。

  それ以外の場合、手順2に進みます。

2.2番目の要素である値に着目し、目的の値であるか比較・確認を行います。

  目的の値であった場合、データの最後尾に設定した値であるかを確認後、

  目的の値であれば、探索は成功で処理は終了です。

  それ以外の場合、3番目の要素の値に進みます。

3.上記を繰り返し探索を行います。

 

 

どんなときに使う?

線形探索は、仕組みがシンプルなため短いプログラムコードで記述できます。
そのため、コードを読んだ人が処理を理解しやすく、探索対象のデータ列以外に余分な記憶領域を消費しません。
また、事前にデータ列のソート(大きい/小さい順に並べ直す処理)などの前処理を行う必要がないというメリットがあります。

番兵法は、上記の線形探索にプラスして処理のコストが半分になるということがメリット言えます。

 

線形探索(番兵法)の実装例(プログラム)

実装例は下記です。

Web上で実際にプログラムを動かすことができるサイトがあります。

色々プログラムをいじってみましょう!

Online PHP/Java/C++... editor and compiler | paiza.IO

 

<実装例>

import java.util.*;

public class Main {

    //線形探索(番兵法)プログラム(コメント)
    static int serch(int a[], int n, int key) {
        int i = 0;
        int b[] = new int[a.length+1]; 
        
        for(int j=0; j<a.length; j++){
            b[j] = a[j];
        }
        
        b[a.length] = key;

        while(true){
            if(b[i] == key){break;}
            i++;
        }
        return i == n ? -1 : i;
    }
    public static void main(String[] args) throws Exception {
        int[] data = {1, 4, 3, 7, 5, 2, 6};
        int r = 7; //探したい値
        int x = serch(data, data.length, r);

        //表示させるプログラム(コメント)
        if (x == -1){
            System.out.println("存在しません");
        }else{
            System.out.println("要素:"+ x +"に対象の値があります。");
        }
    }
}

 

 

 

まとめ

探索の問題に限らず、基礎知識があると問題となっているプログラムに既視感も出て、解きやすくなると考えています!

 

Web上で実際にプログラムを動かすことができるサイトがあります。色々プログラムをいじってみましょう!

Online PHP/Java/C++... editor and compiler | paiza.IO

 

こちらのサイトはjava以外にも対応しています。他の言語で試しても動かすことができます。

アルゴリズムと言われると難しく感じる方もいるかもしれません。ただ、順を追っていけばそこまで難しい話ではないです。まずは触ってみて動きを見てみてはいかがでしょうか。