探索は「あるか」だけでなく位置も答える

名簿から名前を探す、商品番号から商品を取り出す、入力した文字と一致する候補を調べるなど、プログラムには「複数のデータから条件に合うものを見つける」処理が数多くあります。探索の結果として必要なのは、目的の値が存在するかどうかだけとは限りません。見つかったデータの位置、そのデータに結び付いた情報、条件に合う最初の要素などを求める場合もあります。

探索を組み立てるときは、まず「何を手掛かりに、何を答えとして返すか」を決めます。例えば、配列から値を探すなら、値そのものを返すのか、先頭から何番目かを返すのか、見つからなかったことを示す特別な結果を返すのかによって、処理の後半が変わります。同じ値が複数あるときに、どれを採用するかも決めておく必要があります。探索は単なる検索操作ではなく、入力・比較・終了条件・出力を順序立てたアルゴリズムなのです。

線形探索はデータの並び方を選ばない

線形探索では、先頭の要素から順番に目的の値と比較します。一致すればその位置で終了し、末尾まで一致しなければ「見つからない」と判断します。途中の要素を飛ばさないため、昇順や降順に整っていないデータにも使えます。要素を追加した直後で並びが崩れていても、そのまま探せるのが強みです。

一方、目的の値が末尾にある場合や存在しない場合は、すべての要素を確認します。先頭付近にあれば早く終わる可能性はありますが、いつも早いとは限りません。処理を書くときには、比較する位置を一つずつ進めること、見つかった時点で終了すること、最後まで進んだ場合を区別することが要点です。仕組みが単純なので、データが少ない場合や、並べ替える根拠のないデータを一度だけ探す場合には合理的な選択です。

二分探索は中央との比較で候補を捨てる

二分探索が使えるのは、比較の基準に従ってデータが整列している場合です。昇順の数値列から目的の値を探すなら、まず探索範囲の中央を調べます。目的の値が中央の値より小さければ中央より右側は候補から外れ、大きければ左側が候補から外れます。残った範囲で同じ操作を繰り返し、中央と一致すれば探索成功です。候補の範囲がなくなれば、目的の値は存在しないと判断できます。

大切なのは、単に中央の要素を見ることではなく、比較結果を使って「片側には答えがない」と確定できることです。データが未整列なら、中央より小さい値が右側にあるかもしれず、半分を安全に捨てられません。また、文字列なら文字列、日付なら日付というように、整列時と探索時で同じ比較規則を使う必要があります。二分探索の正しさは、この並び順の約束に支えられています。

データが増えたとき比較回数の差が広がる

探索方法の違いは、データ数が増えたときに必要な処理がどう増えるかを見ると明確になります。線形探索は、最悪の場合、要素数に比例して比較回数が増えます。この増え方は O(n) と表します。二分探索では一回の比較ごとに候補がおよそ半分になるため、増え方は O(log n) です。ここでの記号は秒数を直接表すのではなく、入力の大きさに対する処理量の増え方を表します。詳しい考え方は計算量とアルゴリズムの効率と結び付きます。

ただし、計算量だけで必ず実際の速さが決まるわけではありません。データがごく少なければ、単純な線形探索で十分なことがあります。データをどのように保存しているか、比較にどれだけ処理が必要か、追加や削除がどの程度起こるかも影響します。「二分探索の計算量が小さいから常に最適」と決めず、データの状態と利用回数を合わせて考えることが重要です。

見つからなくても「入る場所」が分かる

二分探索には、目的の値が存在しない場合でも役立つ使い方があります。探索範囲を狭めていくと、整列順を保ったまま目的の値を入れられる境目を求められます。例えば、昇順の数値列で「指定した値以上となる最初の位置」を探せば、その位置より前の値はすべて指定値未満だと分かります。この結果は、完全一致の確認だけでなく、範囲検索の開始位置を決める処理にも利用できます。

同じ値が複数並んでいる場合も工夫が必要です。一致した瞬間に終了する通常の二分探索では、同じ値のどれが見つかるかは手順次第です。最初の位置が必要なら、一致した後も左側に同じ値がないか範囲を絞ります。最後の位置が必要なら右側を調べます。「二分探索は値の有無を調べるだけ」という理解ではなく、境界を探す手順としても捉えると応用範囲が広がります。

探す前の整列にも費用がかかる

未整列のデータを二分探索したい場合は、先に整列アルゴリズムで並べる必要があります。ここで、整列に必要な処理を無視してはいけません。一度しか探さない小さなデータなら、整列してから二分探索するより、最初から線形探索する方が手順全体は少なくなることがあります。反対に、同じデータを保ったまま何度も探すなら、最初に整列する費用を、その後の多数の探索で生かせます。

データが頻繁に追加・削除される場合は、並び順を保つ処理も必要です。そのため選択の基準は、探索一回の速さだけではありません。データがすでに整列しているか、探索を何度行うか、更新がどれほどあるか、必要な答えが完全一致か境界位置かを整理すると、線形探索と二分探索を適切に使い分けられます。