Javaで学ぶアルゴリズム -線形探索

線形探索

線形探索（せんけいたんさく、英: linear search, sequential search）は、検索のアルゴリズムの一つ。リストや配列に入ったデータに対する検索を行うにあたって、先頭から順に比較を行い、それが見つかれば終了する。

実行環境

• JUnit 5
• Java 8

テストコード

SequentialSearchTest.java

public class SequentialSearchTest {

	@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(SequentialSearch.sequentialSearch(array, target), is(expected));
	}

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

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

線形探索アルゴリズム

SequentialSearch.java

public class SequentialSearch {

	/**
	 * 線形探索を実行するメソッド。
	 * 配列array内でtargetを探し、そのインデックスを返す。見つからない場合は-1を返す。
	 *
	 * @param array 探索対象の配列、nullが渡される可能性はないと仮定
	 * @param target 探索する値
	 * @return targetのインデックス、見つからない場合は -1 を返す
	 */
	public static int sequentialSearch(int[] array, int target) {
		for (int i = 0; i < array.length; i++) {
			if (array[i] == target) {
				return i;
			}
		}
		return -1;
	}

SequentialSearch.java その２

public class SequentialSearch {

	/**
	 * 線形探索を実行するメソッド。
	 * 配列array内でtargetを探し、そのインデックスを返す。見つからない場合は-1を返す。
	 *
	 * @param array 探索対象の配列、nullが渡される可能性はないと仮定
	 * @param target 探索する値
	 * @return targetのインデックス、見つからない場合は -1 を返す
	 */
	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++;
		}
	}
}