1. 概要

検索の問題はプログラミングで最も一般的なもののいくつかであり、それらを解決する方法はたくさんあります。 これらの方法の2つは、線形検索とバイナリ検索です。

このチュートリアルでは、2つの方法を説明し、それらを比較します。

2. 線形探索

2.1. 理論的アイデア

線形検索は一度に1つのアイテムをスキャンし、あらゆる種類の検索問題を解決するために使用できます。

2.2. 配列内の線形探索

線形検索を使用して、配列内の値を検索できます。 配列のすべての要素を繰り返し処理し、検索された値が見つかったら停止します。 ただし、この種の検索を使用するために条件は必要ないことに注意してください。

説明したアルゴリズムの実装を見てみましょう。

上記のアルゴリズムの合計時間計算量はです。ここで、は配列内の要素の総数です。

2.3. 答えの線形探索

この考えを説明するために例を見てみましょう。

決められたサイズのフルーツジュースのボトルを作りたいとします。 ある程度のお金があり、近くに果物を定価で売っているお店があります。 作成できるボトルの最大数を知りたい。

問題を単純化するために、ボトルの数を入力として受け取る関数があると仮定します。 この関数は、その数のボトルを作るのに十分なお金がある場合は true を返し、それ以外の場合はfalseを返します。

次に、作成できるボトルの最小数から最大数までの範囲を繰り返し、関数を使用してすべての値を確認します。 関数がfalseを返すまで反復を続け、次にアルゴリズムを停止して、私たちが持っているお金で稼ぐことができるボトルの可能な最大数を返します。

説明したアルゴリズムの実装を見てみましょう。

上記のアルゴリズムの合計時間計算量はです。ここで、は範囲の長さです。

3. 二分探索

3.1. 理論的アイデア

二分探索の主なアイデアは、検索範囲を半分に分割することです。 次に、中間値を確認します。 真ん中の値に基づいて、左側または右側のどちらの部分で検索を続行するかを決定します。

3.2. 配列内の二分探索

線形検索とは異なり、バイナリ検索を使用する条件は、配列を並べ替える必要があることです。 配列内の値を検索するとします。 まず、検索範囲の最小値を1と定義します。これは、配列内の最小のインデックスです。 また、最大値を、と定義します。ここで、は配列内の要素の数であり、これは配列内の可能な最大のインデックスです。

その後、複数のステップを実行します。 各ステップで、真ん中の要素を取得し、それが検索している値であるかどうかを確認します。 はいの場合、そのインデックスを返し、アルゴリズムを停止します。

そうでない場合は、2つのオプションがあります。 この中央の要素が検索値よりも大きい場合は、範囲の左側を検索する必要があります。 それ以外の場合、この中央の要素が検索された値よりも小さい場合は、右側の部分を検索します。

説明したアルゴリズムの実装を見てみましょう。

上記のアルゴリズムの合計時間計算量はです。ここで、は配列内の要素の総数です。

3.3. 答えの二分探索

満たすべき条件があるため、問題の答えを探すために常に二分探索を使用できるとは限りません。 特定の値を検索する範囲には、受け入れられる連続部分が1つだけ、受け入れられない連続部分が1つだけ含まれている必要があるという条件があります。

答えの線形探索と同じ例を取り、値の範囲に二分探索を適用してみましょう。

まず、前述したのと同じ機能があると仮定します。 次に、フルーツジュースのボトルの最小数と最大数を定義します。

第三に、複数のステップを実行します。 各ステップで、範囲の中間値を取得し、関数で確認します。 関数がtrueを返す場合、は、作成されるボトルの最大数がこの値またはさらに大きい値のいずれかであることを意味します。 したがって、範囲の右側を検索します。

そうでなければ、はこの数のボトルを作ることができないことを意味し、を作るためにボトルの数を減らすように試みる必要があります。 この場合、左側を検索します。

条件が満たされなくなるまで、このプロセスを繰り返します。 したがって、このようにして、作成できるボトルの最大数が変数内に格納されます。

説明したアルゴリズムの実装を見てみましょう。

上記のアルゴリズムの合計時間計算量はです。ここで、は検索範囲の長さです。

4. 比較

表を見ると、二分探索と線形探索の主な違いがわかります。

つまり、複雑さが低いため、可能であればバイナリ検索の問題を解決するのが最善です。

5. 結論

このチュートリアルでは、線形探索と二分探索を理論的に説明しました。 次に、配列での検索について話し、問題の答えを検索しました。 その後、2つの検索方法を使用して各問題を解決する方法を確認しました。

最後に、2つのアプローチの基本的な比較を示しました。