二分探索 binary search

2020-09-01

こんにちは、0371です。

今回は、配列を二分割していきながら、任意の値が格納されている添字を導き出す方法について書いていきます。
基本情報技術者試験のアルゴリズムの問題集から、擬似言語の問題を実際の言語でプログラミングしてみました。

二分探索 とは？

探索対象となる配列の真ん中の値を、指定した値と比較し、その結果によって探索対象の配列を二分割して狭めていく探索方法です。

コード

今回も、ArrayListを使用して、配列の中から任意の値が格納されている添字を求めます。 言語はJavaです。

main関数内の変数 answerに0~9までの好きな数値を当てはめてください。

任意の値が見つかったら探索を終了するプログラム

Main.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class Main {

	public static void main(String[] args) {
		int listsize = 20;
		int range = 30;
		int answer = 7;

		ArrayList<Integer> list = new ArrayList<>();
		Random rand = new Random();
		for(int i=0; i<listsize; i++)list.add(rand.nextInt(range));
		Collections.sort(list);

		binSearch(list, answer);
	}

	private static void binSearch(ArrayList<Integer> list, int answer) {
		int left = 0;
		int right = list.size()-1;
		int pos = -1;
		boolean notFound = true;

		System.out.println("answer: "+answer);
		System.out.println("left: ["+left+"]"); // 確認用
		System.out.println("right: ["+right+"]"); // 確認用
		System.out.println("元の配列: "+list);
		System.out.println();
		while(pos == -1 && left <= right) {
			ArrayList<Integer> virList = new ArrayList<>(list.size());
			int mid = (left + right)/2;
			System.out.println();
			System.out.println("["+mid+"]番目の添字を見にいきます");
			if(list.get(mid) == answer) {
				pos = mid;
				notFound = false;
				System.out.println("answerと一致しました"); // 確認用
				System.out.println();
			} else if(list.get(mid) > answer) {
				right = mid-1;
				// 確認用のループ
				for(int i = right; i >= left; i--) {
					virList.add(list.get(i));
				}
				System.out.println("["+(right)+"]番目よりも右の添字を除外します");
			} else {
				left = mid+1;
				// 確認用のループ
				for(int i = left; i <= right; i++) {
					virList.add(list.get(i));
				}
				System.out.println("["+left+"]番目よりも左の添字を除外します");
			}
			// 確認用のif文
			if(list.get(mid) != answer) {
				Collections.sort(virList);
				System.out.println(virList+ "(配列の添字の["+left+"]から["+right+"]番目)");
			}
		}
		System.out.println();
		if(notFound) {
			System.out.println(answer+"は、配列の中にはありませんでした。");
		} else {
			System.out.println(answer+"は、配列の添字の"+pos+"番にあります。");
		}
	}
}

確認なしverはこちら

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class Main {

	public static void main(String[] args) {
		int listsize = 20;
		int range = 30;
		int answer = 7;

		ArrayList<Integer> list = new ArrayList<>();
		Random rand = new Random();
		for(int i=0; i<listsize; i++)list.add(rand.nextInt(range));
		Collections.sort(list);

		binSearch(list, answer);
	}

	private static void binSearch(ArrayList<Integer> list, int answer) {
		int left = 0;
		int right = list.size()-1;
		int pos = -1;
		boolean notFound = true;

		System.out.println("answer: "+answer);
		System.out.println("元の配列: "+list);
		System.out.println();
		while(pos == -1 && left <= right) {
			ArrayList<Integer> virList = new ArrayList<>(list.size());
			int mid = (left + right)/2;

			if(list.get(mid) == answer) {
				pos = mid;
				notFound = false;
			} else if(list.get(mid) > answer) {
				right = mid-1;
			} else {
				left = mid+1;
			}
		}
		System.out.println();
		if(notFound) {
			System.out.println(answer+"は、配列の中にはありませんでした。");
		} else {
			System.out.println(answer+"は、配列の添字の"+pos+"番にあります。");
		}
	}
}

Random()とnextInt();を使用することによって、実行するたびに1~30までのランダムなint型の数値を配列の中身へ代入しています。
確認ありverでは、ループ内でvirListという仮の配列を宣言し、ループするごとに探索範囲の表示と初期化を行っています。
また、配列をCollections.sort(list);によって、昇順にソートされた状態にし、二分探索を行います。

binSearch()のwhileループの中では以下のような処理を行っています。

1. 添字のleft+right/2番目とanswerと値が一致するかを比較していきます。
2. 一致する場合はposに添字の値を代入し、answerがpos番目の添字に格納されていることを表示します。
3. answerの方が大きい場合は、left+right/2番目よりも左側の添字を無視して再度1に戻ります。
4. answerの方が大きい場合は、left+right/2番目よりも右側の添字を無視して再度1に戻ります。
5. 添字が見つからない場合は格納されていないことを表示しています。

確認ありverで、何度か実行した結果は以下の通りです。

answer: 7
left: [0]
right: [19]
元の配列: [3, 3, 3, 3, 7, 10, 11, 11, 13, 13, 13, 15, 15, 16, 16, 17, 18, 26, 26, 28]


[9]番目の添字を見にいきます
[8]番目よりも右の添字を除外します
[3, 3, 3, 3, 7, 10, 11, 11, 13](配列の添字の[0]から[8]番目)

[4]番目の添字を見にいきます
answerと一致しました


7は、配列の添字の4番にあります。

answer: 7
left: [0]
right: [19]
元の配列: [0, 0, 0, 1, 1, 3, 5, 6, 6, 6, 7, 8, 9, 11, 14, 17, 19, 24, 25, 28]


[9]番目の添字を見にいきます
[10]番目よりも左の添字を除外します
[7, 8, 9, 11, 14, 17, 19, 24, 25, 28](配列の添字の[10]から[19]番目)

[14]番目の添字を見にいきます
[13]番目よりも右の添字を除外します
[7, 8, 9, 11](配列の添字の[10]から[13]番目)

[11]番目の添字を見にいきます
[10]番目よりも右の添字を除外します
[7](配列の添字の[10]から[10]番目)

[10]番目の添字を見にいきます
answerと一致しました


7は、配列の添字の10番にあります。

answer: 7
left: [0]
right: [19]
元の配列: [0, 3, 4, 4, 6, 6, 8, 8, 12, 15, 16, 17, 17, 19, 21, 26, 27, 28, 28, 28]


[9]番目の添字を見にいきます
[8]番目よりも右の添字を除外します
[0, 3, 4, 4, 6, 6, 8, 8, 12](配列の添字の[0]から[8]番目)

[4]番目の添字を見にいきます
[5]番目よりも左の添字を除外します
[6, 8, 8, 12](配列の添字の[5]から[8]番目)

[6]番目の添字を見にいきます
[5]番目よりも右の添字を除外します
[6](配列の添字の[5]から[5]番目)

[5]番目の添字を見にいきます
[6]番目よりも左の添字を除外します
[](配列の添字の[6]から[5]番目)

7は、配列の中にはありませんでした。

成功していますね。

今日の一言

二分探索もしっかり仕組みを覚えたい。