Pythonでアルゴリズム「二分探索」：調べる範囲を半分に絞るを繰り返す

Pythonでアルゴリズムシリーズ、今回からは、探索アルゴリズム第2弾「二分探索」（バイナリーサーチ）をやってみましょう😆！「探索」というのは、「データから、見つけたい値がどこにあるのかを確認する」ことでしたね。

二分探索って何？

探索方法のなかでも、「二分探索」とは、探す範囲をどんどん半分にしながら、目標の値を絞り込んでいく探索方法です。

処理速度は、「線形探索」より早いです。ただ、データを事前に並べるというひと手間が発生します。

「イメージ湧きません…😑」

ですよね～。説明しますよ～😉。

探す範囲は、どんどん少なるなる

前提として、探すデータは事前に整列（昇順）に並べておいてください。

下準備として、次を行います。

・探す範囲のうちの真ん中にある値を抽出します。
・その真ん中の値と「目標の値」を比較します。

その上で、

・「目標の値」と同じなら、おめでとうございます🧡！値を見つけました！
・「目標の値」の方が大きいなら、真ん中の値の左側（より小さい値がある側）は検索対象から外します。（最初に戻る↑）
・「目標の値」の方が小さいなら、真ん中の値の右側（よい大きい値がある側）は検索対象から外します。（最初に戻る↑）

うーん、言葉だけではよく分からないですね。。。やっぱり絵にしようかな～。皆さんへのサービスです。絵にします！😉

はい、多少分かりやすくなりました！？それなら、私は果報者でござりまする～。

ということで、今日は「二分探索」の導入でした。まだまだ続きますよ～。

では、ビーダゼーン！

※私のやる気アップとブログの品質向上につながりますので、記事が気に入られた方は、「ポチっ」と好きボタンを押してくださったり、フォローいただけますと幸いです🙇。