私たちは日々の生活、車のキー、本、ペン、携帯電話の充電器と何に私たちの日の中で何かを検索する必要がない場合でも、一日のパスではありません。 同じことは、コンピュータの寿命であり、ユーザーがいくつかのデータを要求するたびに、コンピュータは、データを探して、ユーザーが利用できるようにするために、そ そして、コンピュータは、それはあなたが私たちのオペレーティングシステムのチュートリアルシリーズで詳細を学ぶことができ、高速のメモリを検索す
配列内の指定された数値を検索するプログラムを記述する必要がある場合はどうなりますか? どのようにそれを行うのだろうか?
まあ、与えられた配列内の要素を検索するには、利用可能な二つの一般的なアルゴリズムがあります:
- 線形検索
- バイナリ検索
線形検索
線形検索は非常に基本的で単純な検索アルゴリズムです。 線形検索では、最初から目的の要素または値が見つかるまで配列を走査することによって、指定された配列内の要素または値を検索します。
検索する要素を配列に存在するすべての要素と比較し、要素が正常に一致すると、配列内の要素のインデックスを返し、それ以外の場合は-1
を返しま
線形検索は、リスト内の要素が少ない場合、ソートされていないリストまたは順序付けられていないリストに適用されます。
線形探索アルゴリズムの特徴
- これは、要素のソートされていないと順序付けられていない小さなリストのために使用されます。
- 時間の複雑さはO(n)であり、時間は要素の数に線形に依存することを意味しますが、これも悪くはありませんが、それほど良くはありません。
- これは非常に単純な実装です。
次のチュートリアルで線形探索アルゴリズムを実装します。
バイナリ検索
バイナリ検索は、ソートされた配列またはリストで使用されます。 バイナリ検索では、次の手順に従います:
- まず、検索する要素をリスト/配列の中央にある要素と比較します。
- 一致する場合は、中間要素のインデックスを返します。
- 一致が得られない場合は、検索する要素が中央の要素よりもvalueより小さいか大きいかをチェックします。
- 検索する要素/数値が中央の数値よりも大きい場合、中央の要素の右側にある要素を選択します(リスト/配列がソートされているため、右側には中央の数よりも大きいすべての数値が表示されます)、ステップ1から再度開始します。
- 検索する要素/数値が中央の数値よりも小さい場合は、中央の要素の左側にある要素を選択し、ステップ1から再度開始します。
バイナリ検索は、配列内に多数の要素があり、それらがソートされている場合に便利です。したがって、バイナリ検索が機能するために必要な条件は、リスト/配列をソートする必要があることです。
バイナリ検索の特徴
- 大きなソートされた配列を検索するのは素晴らしいことです。
- 時間の複雑さはO(log n)であり、非常に良い時間の複雑さです。 私たちは、バイナリ検索のチュートリアルで詳細にこれを議論します。
- シンプルな実装です。