【Java】線形探索

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

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

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

線形探索(linear search)

逐次探索(sequential search)ともいう。

基本形

先頭から順番に確認していくというシンプルなアルゴリズム。

package chap03;

import java.util.Scanner;

public class SequentialSearch {
	
	//--- 配列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;
	}
	
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		//--- 配列aの用意 ---//
		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");
	}
}

番兵法(sentinel method)

探索要素（Key）を配列の最後に追加して探索を行うアルゴリズム。基本形よりわずかに早い(?)

package chap03;

import java.util.Scanner;

public class SequentialSearchSentinel {
	
	//--- (番兵法)配列aの先頭n個の要素からkeyと一致する要素を線形探索する ---//
	/**
	 * @param a   :配列
	 * @param n   :配列の要素数
	 * @param key :探索する要素
	 * @return 探索成功時：i, 探索失敗時：-1
	 */
	static int seqSearchSen(int[] a, int n, int key) {
		int i = 0;     // カウンタ用変数
		
		a[n] = key;    // 番兵を追加
		
		while (true) {
			if (a[i] == key)
				break;
			i++;
		}
		
		return i == n ? -1 : i;
	}
	
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		//--- 配列aの用意 ---//
		System.out.print("要素数:");
		int   num = stdIn.nextInt();
		int[] x   = new int[num + 1];
		
		//--- 配列aに値を格納する ---//
		for (int i = 0; i < num; i++) {
			System.out.print("x[" + i + "]:");
			x[i] = stdIn.nextInt();
		}
		
		//--- 検索する要素を指定 ---//
		System.out.print("探す値:");
		int key  = stdIn.nextInt();
		
		//--- 探索前の時刻を取得 ---//
		long startTime = System.currentTimeMillis();
		
		//--- 線形探索実行 ---//
		int idx = seqSearchSen(x, num, key);
		
		//--- 探索後の時刻を取得 ---//
		long endTime = System.currentTimeMillis();
		
		//--- 探索結果の表示 ---//
		if (idx == -1)
		System.out.println("その値の要素は存在しません。");
		else
			System.out.println("その値はx{" + idx + "]にあります。");
		
		// 計測結果を表示
		System.out.println("処理時間:" + (endTime - startTime) + "ms");

	}
}

学習内容まとめ

eclipse操作時に役立つショートカットまとめ
https://qiita.com/toshi0383/items/1d2a990392998789062c

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