034-アルゴリズム-二分探索【新人エンジニアが最初に覚えたい100のJava文法】

ユーチューブ動画

アルゴリズム-二分探索について解説します。

ソースコード【2020/5/7訂正後】

public class ArgoSearchBinary {
	public static void main(String[] args) {
		int[] data = { 10, 30, 40, 60, 80, 90, 110, 140, 170, 190, 210, 260 };
		System.out.println(search(data, 140));
	}

	public static int search(int[] data, int target) {
		int ret = -1;
		int left = 0;
		int right = data.length - 1;
		while (left <= right) {
			int mid = (left + right) / 2;
			System.out.println(mid);
			if (data[mid] == target) {
				return mid + 1;
			} else if (target < data[mid]) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}
		return ret;
	}
}

ソースコード【2020/5/7訂正前】

public class ArgoSearchBinary {
	public static void main(String[] args) {
		int[] data = { 10, 30, 40, 60, 80, 90, 110, 140, 170, 190, 210, 260 };
		System.out.println(search(data, 140));
	}
	public static int search(int[] data, int target) {
		int ret = -1;
		int left = 0;
		int right = data.length - 1;
		while(left < right){
			int mid = (left + right) / 2;
			if(data[mid] == target){
				return mid + 1;
			}else if(target < data[mid]){
				right = mid;
			}else{
				left = mid + 1;
			}
		}
		return ret;
	}
}

解説

二分探索について解説します。

プログラムを組み立てるときには、プログラムの解法が必要です。

プログラムの解法をアルゴリズムといいます。

代表的なアルゴリズムを覚えておくと、将来いろいろなプログラムを組むときのヒントになります。

ここでは、二分探索を紹介します。

探索とは、データを探すことです。

二分探索では、データの大小関係に注目して、探索範囲を二分しながら絞り込んでいく方法です。

線形探索に比べると高速な探索アルゴリズムです。

データ量が２倍になっても探索回数は１回しか増えませんから。

ただし、データの大小を見ていくので、データは並び替えされている必要があります。

サンプルコードみていきましょう。

Mainメソッドの中で配列が宣言されています。

すでにソートされています。並び替えの処理は、searchメソッドで定義されています。

配列と探索対象を引数で渡すと、探索結果をかえってくるようにしています。

Searchメソッドでは、変数retに-1を入れておき、戻り値にしています。

探索して、見つからなかった場合には-1を返すようにしています。

二分探索のポイントは、探索範囲をどうするかということです。

変数leftが探索範囲の左端、変数rightが探索範囲の右端としています。

最初の右端は、要素数-1になります。1回目の繰り返しでは、最初は変数leftが0、変数rightが11になります。

Whileを使って、繰り返します。変数leftの値が、変数rightよりも小さいときまで継続するようにします。

逆の場合は見つからなかった場合です。

２分するための中央の値を求めるために、変数leftと変数rightを足して２で割っています。

これを変数midに入れています。

１回目では5になります。

データ型がint型ですから、小数点がでても切り捨てられることに注意してください。

次のifでは、中央の値と探索対象が一致するか調べます。

ここでは、data[5]となるので、90になります。

探索対象と一致したら、1を足したものをreturnしています。

これは配列のインデックスが0から始まるのに対して、私たちは1から数えるからです。

returnすることで、メソッドを終了します。

中央の値と探索対象が一致しない場合には、中央値よりも小さいか大きいかを判断しています。

それがelse if elseの部分です。

中央値よりも小さい場合は、変数midを変数rightに、大きい場合は、変数midに1足したものを変数leftにすることで、探索範囲を狭くしています。

今回は、中央値が90で、探索対象が140が入っているので、elseifには入らずelseに入り、変数leftの値が6になります。

これは変数midに5が入っていて、変数leftに6が入るからです。２回目の繰り返しでは、変数leftが６，変数rightが11になります。

変数midが8になり、探索対象140とdata[8]すなわち170と比較します。

探索対象の方が小さいので、変数rightが8になります。　　　

３回目の繰り返しで、変数midが7になり、探索対象140とdata[7]すなわち140が一致という形になりますから、8番目の8を返して終了します。　　　

いかがでしたか？最初は混乱するかもしれませんが、１回目ではどうだ、２回目ではどうだとゆっくり考えてみてください。

それを繰り返すと速く考えられるようになります。

以上、二分探索について解説しました。

このサンプルコードをJavaタッチタイプゲームとして遊ぶことができます。