感謝のプログラミング 10000時間

たどり着いた結果(さき)は、感謝でした。

Javaで2分探索のサンプル

<スポンサーリンク>

2分探索とは、英語でbinary searchといって、要素がキーの昇順または降順にソートされている配列から効率よく探索を行うアルゴリズムのこと。

2分探索の方法は単純で、対象の配列を真ん中から半分に割って、ターゲットの数字が右側にあるか(真ん中の数字より大きいか)、左側にあるか(真ん中の数字より小さいか)で半分ずつ分けていく。

たとえば、右側にあることがわかったなら、今度は「配列の真ん中から右側」を対象に、同じようにまた、真ん中から分けて探索していく。
ちょうど真ん中がターゲットの数字だったら探索成功。
探索対象がなくなったら探索失敗というようになる。

実際のアルゴリズムの実装はこんな感じ。

package algorithm.search;

public class BinarySearch {
	public int binarySearch(int[] array, int key) {
		int pLeft = 0;
		int pRight = array.length - 1;

		do {
			int center = (pLeft + pRight) / 2;

			if (array[center] == key) {
				return center;
			} else if (array[center] < key){
				pLeft = center + 1; //真ん中の一つ右側を左端とする
			} else {
				pRight = center - 1;
			}
		} while (pLeft <= pRight);

		return -1;
	}

	public void see(int[] array) {
		System.out.println("対象の配列は以下のとおりです");
		for(int i=0;i<array.length;i++) {
			if (i != array.length - 1) {
				System.out.print(array[i] + ",");
			} else {
				System.out.println(array[i]);
			}
		}
	}

}

上記の探索アルゴリズムを活用してみる。

package algorithm.search;

import java.util.Arrays;
import java.util.Random;

public class BinarySearchMain {
	public static void main(String[] args) {
		int size = 20;
		int max = 30;
		int target = 11;
		int[] array = new int[size];
		int targetIndex = -1;

		Random rnd = new Random();
		for (int i=0;i < array.length; i++) {
			array[i] = rnd.nextInt(max);
		}

		BinarySearch binSearch = new BinarySearch();
		binSearch.see(array);
		//前提条件として、ソートを行う
		System.out.println("とりあえずソートします");
		Arrays.sort(array);
		binSearch.see(array);

		targetIndex = binSearch.binarySearch(array,target);
		if (targetIndex != -1) {
			System.out.println(target + " は[" + (targetIndex + 1) + "] 番目に存在します");
			System.out.println("array[" + targetIndex + "] = " + array[targetIndex]);
		} else {
			System.out.println("ターゲットは存在しません");
		}


	}
}

で、こいつらを使った結果は以下のようになる。

対象の配列は以下のとおりです
21,4,16,18,19,22,3,4,26,1,12,19,0,3,18,19,20,17,11,13
とりあえずソートします
対象の配列は以下のとおりです
0,1,3,3,4,4,11,12,13,16,17,18,18,19,19,19,20,21,22,26
11 は[7] 番目に存在します
array[6] = 11

上記のように、それっぽく探索することができた。

参考

明解 Javaによるアルゴリズムとデータ構造

明解 Javaによるアルゴリズムとデータ構造

おなじみだけど、図が豊富でわかりやすい。
定番の本。オライリーのアルゴリズム本の前に読んでいる。