探索アルゴリズム可視化

2つの探索の違い

線形探索 … 先頭から1つずつ順に目標と比べる。整列していなくても使えるのが利点だが、データが n 個あると最悪 n 回の比較が必要（計算量 O(n)）。
二分探索 … 整列済みであることが前提。真ん中の値と比べ、目標が大きければ右半分・小さければ左半分、と毎回探す範囲を半分に絞る。n 個でも約 log₂n 回で済む（計算量 O(log n)）。

個数スライダーを最大（31個）にして、同じ目標を線形探索と二分探索で探し比べてみてください。線形探索は最大31回かかることがありますが、二分探索は最大でも5回（2⁵=32）で見つかります。データが100万個でも二分探索なら約20回です。これが「整列しておくと探索が速くなる」理由です。

二分探索の落とし穴

並んでいないデータには使えません。 二分探索は「真ん中より大きいか小さいか」で半分を捨てるので、昇順（または降順）に整列していることが大前提です。未整列のデータを二分探索すると、正しく見つけられません。「探す前に並べておく」のがセットの考え方です。

基本情報技術者試験ではこう出る

科目Aでは計算量の比較（線形探索は O(n)、二分探索は O(log n)）や、「データ数が増えたとき比較回数がどう変わるか」がよく問われます。科目Bでは、二分探索の擬似言語コードを読んでlo（下限）・mid（中央）・hi（上限）がどう更新されるかをトレースする問題が頻出です。本ツールの lo / mid / hi マーカーの動きと、コードの lo ← mid + 1 や hi ← mid - 1 を対応させて覚えると、トレースが格段に読みやすくなります。整列が必要な点も狙われます。

よくある質問

Q. 目標が配列にないときは？
A. 「別の問題」を何度か押すと、配列に存在しない値が目標になることがあります。その場合、線形探索は最後まで全部確認し、二分探索は範囲（lo と hi）が交差した時点で「見つからない」と判断して終わります。

Q. プログラムではどう書く？
A. 多くの言語に標準の二分探索があります（Pythonの bisect、Javaの Arrays.binarySearch など）。仕組みを理解したうえで、実務ではこうした標準ライブラリを使うのが安全です。ソートの仕組みは当サイトのソートアルゴリズム可視化で確認できます。