プログラム

二分探索とは

2021年3月20日

二分探索

二分探索(にぶんたんさく)とは、探索アルゴリズムの1つです。

配列やリストのような複数のデータが格納されている箱の中から、目的のデータを探し出すのが探索であり、この探索の代表的なアルゴリズムには「線形探索」「二分探索」「ハッシュ法」があります。

本記事では、探索対象の配列やリストを「昇順」または「降順」に並び替えて探索する「二分探索」について紹介しています。

スポンサーリンク

二分探索の手順(データが見つかる場合の例)

二分探索は「昇順」または「降順」に並んでいる配列やリストに対して探索を行う手法です。探索対象を1/2ずつ削り落としていくので効率よく探索することができます。

今回の例では、「昇順」に並んでいる次の配列から「6」を二分探索で探索する手順を説明していきます。

二分探索開始

【手順1】位置1~8の真ん中のデータ「7」と比較

まずは位置1~8の中央位置を計算します。(最小位置:1、最大位置:8)

中央位置の計算方法は次の通り。

最小位置 + (最大位置 - 最小位置) / 2

中央位置を求めると、1 + (8 - 1) / 2 = 4

配列の中央位置は4なので、位置4のデータ「7」と比較。比較した結果「6」の方が小さいので、探索の範囲を左半分に絞り込みます

位置1~8の真ん中、位置4のデータ「7」と比較

【手順2】位置1~3の真ん中のデータ「3」と比較

続いては位置1~3の中央位置を計算します。(最小位置:1、最大位置:3)

中央位置を求めると、1 + (3 - 1) / 2 = 2

配列の中央位置は2なので、位置2のデータ「3」と比較。比較した結果「6」の方が大きいので、探索の範囲を右半分に絞り込みます

位置1~3の真ん中、位置2のデータ「3」と比較

【手順3】「6」を見つけることができたので処理終了

続いては位置3のデータ「6」と比較、「6」を見つけることができたので処理終了です。

位置3のデータ「6」と比較

二分探索の手順(データが見つからない場合の例)

今回の例では、「昇順」に並んでいる次の配列から「18」を二分探索で探索する手順を説明していきます。

二分探索、見つからない場合の例

【手順1】位置1~8の真ん中のデータ「7」と比較

まずは位置1~8の中央位置を計算します。(最小位置:1、最大位置:8)

中央位置を求めると、1 + (8 - 1) / 2 = 4

配列の中央位置は4なので、位置4のデータ「7」と比較。比較した結果「18」の方が大きいので、探索の範囲を右半分に絞り込みます

位置1~8の真ん中、位置4のデータ「7」と比較

【手順2】位置5~8の真ん中のデータ「17」と比較

続いては位置5~8の中央位置を計算します。(最小位置:5、最大位置:8)

中央位置を求めると、5 + (8 - 5) / 2 = 6

配列の中央位置は6なので、位置6のデータ「17」と比較。比較した結果「18」の方が大きいので、探索の範囲を右半分に絞り込みます

位置5~8の真ん中、位置6のデータ「17」と比較

【手順3】位置7~8の真ん中のデータ「20」と比較

続いては位置7~8の中央位置を計算します。(最小位置:7、最大位置:8)

中央位置を求めると、7 + (8 - 7) / 2 = 7

配列の中央位置は7なので、位置7のデータ「20」と比較。比較した結果「18」の方が小さいので、探索の範囲を左半分に絞り込みます

位置7~8の真ん中、位置7のデータ「20」と比較

【手順4】「18」は見つからなかったので処理終了

位置7の左側はすでに確認済みのため、そこにはデータが存在しないことがわかっています。

「18」は見つからなかったので処理終了です。

「18」は見つからなかったので終了

helpful