Javaで学ぶアルゴリズム -二分探索（.binarySearch ver.）

二分探索

上記のロジックは java.util.Arrays にあるのでそれを使うとよいです。

メソッドの仕様はJavaDocに詳細に書いてくれてますね。多少意訳すると以下のような感じ。

• 指定された int 配列から、指定された値をバイナリ検索アルゴリズムで検索する
• 呼び出す前に、任意のキーで配列はソートされている必要がある（ソートされていない場合、結果は意図したものにならない）
• 配列に指定された値を持つ要素が複数ある場合、どの値を返すかは保証しない
• 配列内に指定された値がある場合はそのインデックスを返すが、存在しない場合はその値が次に挿入されるべき位置を負の数で返す

実行環境

• 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, -9",
			"29, 14",
			"31, -16"
	})
	void testNormalBinarySearch(int target, int expected) {
		// ソート後の配列 { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29 };
		int[] array = { 23, 7, 1, 5, 11, 3, 29, 21, 13, 27, 15, 25, 19, 9, 17 };
		assertThat(BinarySearch.SortAndBinarySearch(array, target), is(expected));
	}

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

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

二分探索アルゴリズム

BinarySearch.java

import java.util.Arrays;

public class BinarySearch {

	/**
	 * 配列をソートし、二分探索を実行するメソッド。
	 * ソートしたarray内でtargetを探し、そのインデックスを返す。
	 * 見つからない場合はキーが挿入されるべき位置を示すためのインデックスを「負の数」にして返す。
	 *
	 * @param sortedArray 探索対象のソート済み配列（昇順）
	 * @param target 探索する整数値
	 * @return targetのインデックス、見つからない場合は-1を返す
	 */
	public static int SortAndBinarySearch(int[] array, int target) {

		// 1. 配列をソートする
		Arrays.sort(array);

		// 2. 二分探索を行う
		return Arrays.binarySearch(array, target);
	}
}