Javaで学ぶアルゴリズム -線形探索（番兵法ver.）

番兵法

• 配列やリストの末尾に探索対象の値（いわゆる「番兵」となる値）を追加する
• これにより、ターゲットが見つからなかった場合にループを終了するための追加の条件チェックが不要になる
• 結果としてアルゴリズムが ﾁｮｯﾄ シンプルになり、場合によってはパフォーマンスが向上するカモ

実行環境

• JUnit 5
• Java 8

テストコード

SequentialSearchWithSentinelTest.java

public class SequentialSearchWithSentinelTest {

	@DisplayName("正常系テスト")
	@ParameterizedTest(name = "No.{index}: {0}を探すとインデックス{1}を返す")
	@CsvSource(value = {
			"-1, -1",
			"1, 0",
			"5, 4",
			"10, 9",
			"11, -1"
	})
	void testNormalSequentialSearch(int target, int expected) {
		int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
		assertThat(SequentialSearchWithSentinel.sequentialSearchWithSentinel(array, target), is(expected));
	}

	@DisplayName("配列が空である場合、-1を返す")
	@Test
	void testEmptyArray() {
		int[] array = {};
		assertThat(SequentialSearchWithSentinel.sequentialSearchWithSentinel(array, 1), is(-1));
	}

	@DisplayName("重複する要素がある場合、最初に見つかったインデックスを返す")
	@Test
	void testDuplicateElements() {
		int[] array = { 1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10 };
		assertThat(SequentialSearchWithSentinel.sequentialSearchWithSentinel(array, 4), is(3));
	}
}

番兵法を使った線形探索アルゴリズム

ループの終了条件（探索したい値が見つからずにすべて通り過ぎたか？）が1つ減るので、大量のデータセットを扱う場合には処理の効率が上がるかもしれません。

SequentialSearchWithSentinel.java

public class SequentialSearchWithSentinel {

	/**
	 * 線形探索を番兵法を用いて実行するメソッド。
	 * 配列array内でtargetを探し、そのインデックスを返す。見つからない場合は-1を返す。
	 *
	 * @param array 探索対象の配列、nullが渡される可能性はないと仮定
	 * @param target 探索する値
	 * @return targetのインデックス、見つからない場合は -1 を返す
	 */
	public static int sequentialSearchWithSentinel(int[] array, int target) {

		// 配列のサイズを1増やす
		int[] arrayWithBanpei = Arrays.copyOf(array, array.length + 1);
		// 配列の最後に番兵を追加
		arrayWithBanpei[array.length] = target;

		int i;
		for (i = 0; arrayWithBanpei[i] != target; i++) {
			// ループ内の動作はすべてfor文に含まれているので記述不要
		}
		// 配列の本来の範囲外（番兵の位置）で見つかった場合は -1 を返す
		return i == array.length ? -1 : i;
	}

    // =======以下、番兵法を使わない場合（比較用）=======
	public static int sequentialSearch(int[] array, int target) {
		for (int i = 0; i < array.length; i++) {
			if (array[i] == target) {
				return i;
			}
		}
		return -1;
	} 
}

SequentialSearchWithSentinel.java その2

public class SequentialSearchWithSentinel {

	/**
	 * 線形探索を番兵法を用いて実行するメソッド。
	 * 配列array内でtargetを探し、そのインデックスを返す。見つからない場合は-1を返す。
	 *
	 * @param array 探索対象の配列、nullが渡される可能性はないと仮定
	 * @param target 探索する値
	 * @return targetのインデックス、見つからない場合は -1 を返す
	 */
	public static int sequentialSearchWithSentinel(int[] array, int target) {

		// 配列のサイズを1増やす
		int[] arrayWithBanpei = Arrays.copyOf(array, array.length + 1);
		// 配列の最後に番兵を追加
		arrayWithBanpei[array.length] = target;

		int i = 0;
		while (arrayWithBanpei[i] != target) {
			i++;
		}
		// 配列の本来の範囲外（番兵の位置）で見つかった場合は -1 を返す
		return i == array.length ? -1 : i;
	}
 
    // =======以下、番兵法を使わない場合（比較用）=======
	public static int sequentialSearch(int[] array, int target) {
 
		int i = 0;
  
		while (true) {
			if (i == array.length) {
				return -1;
			}
			if (array[i] == target) {
				return i;
			}
			i++;
		}
	}
}

補足

番兵法使わないやつ