【Java アルゴリズム修行⑥】線形探索と番兵法

14948 ワード
Java11 Java アルゴリズム Java テキストリンク

方法論を学ぶことも大事そう

問題を解いて、自力で解法を得る思考回路を作るのも大事ですが、
先人が既に定義してくれている解法を勉強することも同じくらい大事ということで
今回は線形探索について学んだことを書いてみたいと思います！

線形探索とは？？

配列からの何か特定の要素を探すアルゴリズムとしては基本中の基本だそうです。

要素が直線状に並んだ配列から要素を探すとき、目的とする値を持つ要素に出会うまで先頭から順に要素を走査することで実現できる

というのが、線形探索、もしくは逐次探索と呼ばれるアルゴリズムとのことで、、
頭から順番に、探している要素と同じですか？っていうのを聞いて回って、一緒だったらそいつです！っていうシンプルな話みたいですね。。

そんな線形探索ですが、永遠に走査するわけではなく下記のような終了条件があるそうです。

  • 探索すべき値が見つからず終端を通り越したとき
  • 探索すべき値と等しい要素を見つけたとき

ふむふむ。見つからずに最後までいっちゃったか、見つけたかどっちかという感じですかね。
早速コードで表現してみましょう。

java.algo
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int count = sc.nextInt();
    int array[] = new int[count];
    for (int i = 0; i < count; i++) {
      array[i] = sc.nextInt();
    }
    System.out.print("探す値: ");
    int target = sc.nextInt();
    int answer = search(array, count, target);
    if (answer == -1) {
      System.out.println("探索失敗");
    } else {
      System.out.println(++answer + "番目に存在します");
    }
  }

  public static int search(int[] array, int n, int key) {
    int i = 0;
    //制御文をtrueとして無限ループ
    while (true) {
      //最後のインデックスまでいってしまえば探索失敗
      if (i == n) {
        return -1;
      // キー値と同一であれば該当インデックスを返却
      } else if (array[i] == key) {
        return i;
      }
      i++;
    }
  }
}

最初に入力された数分だけの要素を持つ配列を生成し、要素分だけ配列に要素を詰めていきます。
その配列から線形探索を用いて、キー値（探している値）の位置を取得するという流れです。

線形探索を行っているのはsearchメソッドですが、中身ではwhile文の制御文をtrueとすることで無限ループを行っています。
無限ループといっても、return文やbreak文があれば抜けることができるので、先の終了条件2つに合わせて条件分岐を設定しましょう。

(n == i)のときに、ループ数が配列の要素数を超えてしまった場合と、(array[i] == key)のときが、キー値と配列の要素が一緒だった場合の2つで分岐させました。
前者は探索が失敗しているので、インデックスには存在しえない -1 を返し、キー値が存在した場合はインデックスを返すようにしています。

先頭から全ての要素を探す流れを無限ループで実現するというのは新鮮でしたね。。
ここではwhile文で実現していますが、for文でも以下のように実現可能です。

algo.java
  public static int search(int[] array, int n, int key) {
    for(int i = 0; i < n; i++){
      if(array[i] == key){
        return i;
      }
    }
    return -1;
  }

for文ではループ数を条件文で制御することができるので、
キー値と一致する要素はなくfor文を抜ける = キー値は存在しないので -1を返す という流れでwhile文より簡潔に書くことができますね！

番兵法

while文で実現した場合、繰り返しの度に2つの終了条件の両方をチェックする
ことになりますが、この計算コストはバカになりません。。

このコストを半分にできるのが番兵法というものです。

例えば、10個要素がある配列の中で、2という値を探したいとなったとき、11個目の要素に2を入れてしまい、
その上で線形探索を行うというものです。

これだけ聞くと、「ん？走査する要素を増やしているだけで、効率上がるのか？」と自分でも思いましたが、実際にコードで表現してみましょう。

algo.java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        //番兵用に要素を1つ追加しておく
        int array [] = new int[count + 1];
        for(int i = 0; i < count; i++){
            array[i] =  sc.nextInt();
        }
        System.out.print("探す値: ");
        int target = sc.nextInt();
        int answer = search(array,count,target);
        if(answer == -1){
            System.out.println("探索失敗");
        }else{
            System.out.println(++answer +"番目に存在します");
        }
    }

    public static int search(int [] array, int n, int key){
        int i = 0;
        //末尾に番兵（キー値）を代入
        array[n] = key;
        while(true){
            //キー値と一致していればその時点でループを抜ける
            if(array[i] == key){
                break;
            }
            i++;
        }
        //一致したインデックスが最後（番兵）であれば探索失敗、そうでなければ本来のデータ
        return i == n ? -1 : i;
    }
}

初期のwhile文では下記の条件をif文で確かめていましが、

  • 探索すべき値が見つからず終端を通り越したとき
  • 探索すべき値と等しい要素を見つけたとき

番兵法を使うことで、これを(array[i] == key)という条件式だけで判断することができるんですね！

もし本来の配列データにキー値と一致するものがなければ、末尾に追加したキー値（番兵）に辿り着くので、いずれにせよwhile文のループは抜けることができるということです、、（考えついた人の頭の柔らかさが欲しい）

ループ後は、return i == n ? -1 : i; でループ回数(i)と要素数（n）が一致していれば、末尾までの番兵までたどり着いたということになるので、-1を返しています。
（nは最初の入力値である配列要素の数ですが、配列のインデックスは0から始まるので、n個の要素で成り立つ配列に追加した末尾のインデックスはnになるということですね！）

この番兵を追加するだけで、終端を通り過ぎてしまったときの終了判定であった（i == n）の判定が不要になり、実質判定回数を半分にすることができました。。！

学んだこと

  • 既に定義されているアルゴリズムは積極的に学んだ方が良さそう
  • for文の中の条件式を半分にすれば、全体の判定回数も半分にできる

線形探索、、前から順番に探索するだけか　とか思っていましたが、while文での無限ループや番兵方による判定回数の減らし方など、自分の中の手札として知っておくだけで違うことを学べたので、ここは引き続きインプットとアウトプットを続けていこうと思います！