ユーチューブ動画

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

 

ソースコード

解説

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1回目では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が入るからです。2回目の繰り返しでは、変数leftが6,変数rightが11になります。

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

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

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

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

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

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

 

 

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