Javaで学ぶアルゴリズム -二分探索

二分探索

ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。
大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。

実行環境

• JUnit 5
• Java 8

テストコード

BinarySearchTest.java

public class BinarySearchTest {

	@DisplayName("正常系テスト")
	@ParameterizedTest(name = "No.{index}: {0}を探すとインデックス{1}を返す")
	@CsvSource(value = {
			"-1, -1",
			"1, 0",
			"7, 3",
			"16, -1",
			"29, 14",
			"31, -1"
	})
	void testNormalBinarySearch(int target, int expected) {
		int[] sortedArray = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29 };
		assertThat(BinarySearch.binarySearch(sortedArray, target), is(expected));
	}

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

	@DisplayName("要素が複数存在する場合、最初に見つかったインデックスを返す")
	@ParameterizedTest(name = "No.{index}: {0}を探すとインデックス{1}を返す")
	@CsvSource(value = {
			"2, 1",
			"4, 4",
			"6, 6"
	})
	void testWithDuplicateElements(int target, int expected) {
		int[] sortedArray = { 1, 2, 2, 4, 4, 6, 6, 6, 7 };
		assertThat(BinarySearch.binarySearch(sortedArray, target), is(expected));
	}
}

二分探索アルゴリズム

BinarySearch.java

public class BinarySearch {

	/**
	 * 二分探索を実行するメソッド。
	 * ソート済みの配列sortedArray内でtargetを探し、そのインデックスを返す。見つからない場合は-1を返す。
	 *
	 * @param sortedArray 探索対象のソート済み配列（昇順）
	 * @param target 探索する整数値
	 * @return targetのインデックス、見つからない場合は-1を返す
	 */
	public static int binarySearch(int[] sortedArray, int target) {

		int start = 0;
		int end = sortedArray.length - 1;

		while (start <= end) {
			int mid = start + (end - start) / 2; // 中央のインデックスを計算

			if (sortedArray[mid] == target) {
				return mid;
			} else if (sortedArray[mid] < target) {
				start = mid + 1; // 探索範囲を右半分へ
			} else {
				end = mid - 1; // 探索範囲を左半分へ
			}
		}
		return -1;
	}
}