034-アルゴリズム-二分探索【新人エンジニアが最初に覚えたい100のJava文法】シミュレーターあり
山崎講師ユーチューブ動画
アルゴリズム-二分探索について解説します。
ソースコード
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;
}
}解説
二分探索について解説します。
プログラムを組み立てるときには、プログラムの解法が必要です。
プログラムの解法をアルゴリズムといいます。
代表的なアルゴリズムを覚えておくと、将来いろいろなプログラムを組むときのヒントになります。
ここでは、二分探索を紹介します。
探索とは、データを探すことです。
二分探索では、データの大小関係に注目して、探索範囲を二分しながら絞り込んでいく方法です。
線形探索に比べると高速な探索アルゴリズムです。
データ量が２倍になっても探索回数は１回しか増えませんから。
ただし、データの大小を見ていくので、データは並び替えされている必要があります。
サンプルコードみていきましょう。
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タッチタイプゲームとして遊ぶことができます。
投稿者プロフィール
- 代表取締役
-
セイ・コンサルティング・グループ株式会社代表取締役。
岐阜県出身。
2000年創業、2004年会社設立。
IT企業向け人材育成研修歴業界歴20年以上。
すべての無駄を省いた費用対効果の高い「筋肉質」な研修を提供します！
この記事に間違い等ありましたらぜひお知らせください。
最新の投稿
新入社員2024年11月23日「ゲシュタルト崩壊」とシステム開発- 新入社員2024年11月23日データベースでテーブル名やフィールド名にスペースを使うことは、一般的には推奨されていません
- 新入社員2024年11月23日「データにはなぜ型が必要なのか？」を2進数の観点から解説
- 新入社員2024年11月23日ディスプレイの解像度の意味と変更方法
