【Java】線形探索

この記事は、「新・明解Javaで学ぶアルゴリズムとデータ構造」を読んで学んだことをまとめています。

ただし、本を参考にして自分なりに構成やコードを変更しているためご注意ください。
アルゴリズムの詳細や解説は是非参考書をお手に取って読まれてください。

【リンク紹介】
・Javaで学ぶアルゴリズムとデータ構造
・これまで書いたシリーズ記事一覧

この記事は探索アルゴリズムの線形探索についてまとめました。

基本用語確認

アルゴリズム

問題を解くためのものであって、明確に定義され、順序付けられた有限個の規則からなる集合。
（「JIS X0001」より。JISとは日本産業規格のこと。）

探索アルゴリズム

データの集合の中から目的とする値をもった要素を探し出すアルゴリズム。

計算量

計算量（complexity）とは、アルゴリズムの性能を評価するための尺度である。計算量は次の２つに大別される。

• 時間計算量（time complexity）
  実行に要する時間を評価したもの。アルゴリズムの処理や操作回数で表す。
• 領域計算量（space complexity）
  どのくらいの記憶域やファイル域が必要であるかを評価したもの。

このとき、データ数$n$に対する時間計算量を$\mathcal{O}$を用いて表す。例えば、$\mathcal{n^2}$とは、時間計算量がデータ数$n$に対して$n^2$に比例することを意味する。以降は時間計算量のことを単に計算量と呼ぶこととする。

計算量の大小関係は次のとおりである。

$$\mathcal{O}(1) < \mathcal{O}(\log n) < \mathcal{O}(n) < \mathcal{O}(n \log n) < \mathcal{O}(n^k) < \mathcal{O}(2^n)$$

線形探索

要素が直線状に並んだ配列において、先頭から順番に要素を確認する探索アルゴリズムを線形探索(linear search)または逐次探索(sequential search)という。計算量は$\mathcal{O}(n)$。

線形探索の実装

Java

//--- 配列aの先頭n個の要素からkeyと一致する要素を線形探索する ---//
/**
 * @param a   :配列
 * @param n   :配列の要素数
 * @param key :探索する要素
 * @return 探索成功時：i, 探索失敗時：-1
 */
static int seqSearch(int[] a, int n, int key) {
  for (int i = 0; i < n; i++)
    if (a[i] == key)
      return i;
  return -1;
}

while文による実現

「新・明解Javaで学ぶアルゴリズムとデータ構造」ではwhile文を用いたものを採用しています。こちらは要素の最後にたどり着くか、目的の値を見つけるかのいずれかが成立した場合に終了する記述になっています。

Java

// 線形探索（while文）
static int seqSearch(int[] a, int n, int key) {
  int i = 0;  // カウンタ用変数

  while (true)
    // 探索失敗
    if (i == n)
      return -1;
    // 探索成功
    if (a[i] == key)
      return i;
    i++;
}

番兵法

while文を用いた線形探索では、while文が実行される間は常に２つの判定をしなければなりません。ところが、番兵法(sentinel method)という探索要素（Key）を配列の最後に追加して探索を行う手法を用いると、while文よりも判定コストを半分に抑えることができます。

Java

// 線形探索（番兵法）
static int seqSearch(int[] a, int n, int key) {
  int i = 0;   // カウンタ用変数	
  a[n] = key;  // 番兵を配列の最後に追加

  while (true) {
    if (a[i] == key)
      break;
    i++;
  }

  // i == nがtrueとは、最後まで目的の要素が見つからなかったということ	
  return i == n ? -1 : i;
}

線形探索の利用例

最初に紹介したfor文による線形探索を用いて実装例を以下に記述します。

Java

import java.util.Scanner;

public class SequentialSearch {

  // 線形探索
  static int seqSearch(int[] a, int n, int key) {
    for (int i = 0; i < n; i++)
      if (a[i] == key)
        return i;
    return -1;
  }

  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
	
    //--- 配列aの用意 ---//
    System.out.println("【線形探索】");
    System.out.print("要素数:");
    int   num = stdIn.nextInt();
    int[] x   = new int[num];
	
    //--- 配列aに値を格納する ---//
    for (int i = 0; i < num; i++) {
      System.out.print("x[" + i + "]:");
      x[i] = stdIn.nextInt();
    }

    //--- 検索する要素を指定 ---//
    System.out.print("探す値:");
    int ky = stdIn.nextInt();
	
    // 探索前の時刻を取得
    long startTime = System.currentTimeMillis();
	
    //--- 線形探索実行 ---//
    int idx = seqSearch(x, num, ky);
		
    // 探索後の時刻を取得
    long endTime = System.currentTimeMillis();
		
    //--- 探索結果の表示 ---//
    if (idx == -1)
      System.out.println("その値の要素は存在しません。");
    else
      System.out.println("その値はx[" + idx + "]にあります。");
		
    // 計測結果を表示
    System.out.println("処理時間:" + (endTime - startTime) + "ms");
  }
}

実行結果

【線形探索】
要素数:5
x[0]:35
x[1]:28
x[2]:61
x[3]:94
x[4]:38
探す値:94
その値はx[3]にあります。
処理時間:0ms

$\bf{\textcolor{red}{記事が役に立った方は「いいね」を押していただけると、すごく喜びます \ 笑}}$
ご協力のほどよろしくお願いします。