線形検索と二分探索をする

解説

Javaの配列の中から目的の値を検索する、アルゴリズムを実現するコードを作ってみたので

その時のロジックを紹介します！

記憶にないですが、確か、プログラミングコンテスト向けに勉強したときのものだと思います。

どなたかの参考になれば、、、、と思います。

（総称型を使って、大体の型で使えるように意識して作ってます。）

ソースコード

public static void main(final String... args) {
		
	final Integer[] values = new Integer[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	
	System.out.println("linear binary");
	System.out.println(linear(5, Arrays.asList(values)) + " " + binary(5, values));
	System.out.println(linear(2, Arrays.asList(values)) + " " + binary(2, values));
	System.out.println(linear(7, Arrays.asList(values)) + " " + binary(7, values));
	System.out.println(linear(0, Arrays.asList(values)) + " " + binary(0, values));
	System.out.println(linear(10, Arrays.asList(values)) + " " + binary(10, values));
	System.out.println(linear(-1, Arrays.asList(values)) + " " + binary(-1, values));
	System.out.println(linear(11, Arrays.asList(values)) + " " + binary(11, values));
}

/**
	* 線形検索（List.indexOfで代用可能）
	* 
	* n個のデータを１つずつ見て見つける
	* 
	* @param key
	* @param values
	* @return
	*/
public static <T> int linear(final T key, final Iterable<T> values) {
	
	int index = 0;
	for (final T value : values) {
		if(value.equals(key))
			return index;
		index++;
	}
	return -1;
}

/**
	* 二分探索（List.indexOfで代用可能）
	* 
	* n個のデータが左から小さい順に並んでいること
	* 
	* 中央のデータを見る
	*  ⇒ 中央データ値より大きい ⇒ 中央より右側半分をみる
	*  ⇒ 中央データ値より小さい ⇒ 中央より左側半分をみる
	* 
	*  （以降、見つかるまで繰り返し）
	* 
	* @param key
	* @param values
	* @return
	*/
public static <T extends Comparable<T>> int binary(final T key, final T[] values) {
	
	final int length = values.length;
	
	int index = length / 2;
	//System.out.println("index=" + index);
	
	T value = values[index];
	int result = key.compareTo(value);
	
	while (result != 0 && index != 0) {
		if(result < 0)
			index = index / 2;
		else
			index += index / 2;
		
		if(length <= index )
			break;
		
		//System.out.println("index=" + index);
		
		value = values[index];
		result = key.compareTo(value);
	}
	if(result == 0)
		return index;
	else
		return -1;
}