About
本サイトについて
趣味で開発したプログラムや開発メモを載せています。
ソースコードはGithubで公開しつつ、なるべく後から分かるように解説に努めてますので、
誰かのお役に立てれば嬉しいです。
プロフィール
kght6123
佐賀県出身で1985年生まれ。
三重県四日市市在住のシステムエンジニア。家庭を大事にしたい2児の父。
線形検索と二分探索をする
解説
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;
}