二分探索アルゴリズム

二分探索は二分探索とも呼ばれ、より効率的な検索方法です。ただし、二分探索では、線形テーブルが逐次記憶構造を採用し、テーブル内の要素がキーワード順に配置されている必要があります。

#検索処理

まず、テーブル内の要素が昇順に並んでいると仮定して、キーを記録します。テーブルの中央 単語と検索キーワードが比較され、両者が等しい場合、検索は成功します。そうでない場合は、中央の位置のレコードを使用してテーブルが最初と最後のサブテーブルに分割されます。中間位置に記録されているサブテーブルが検索キーワードより大きい場合は前のサブテーブルをさらに検索し、そうでない場合はさらに次のサブテーブルを検索します。条件を満たすレコードが見つかって検索が成功するまで、またはサブテーブルが存在しない場合は検索が失敗するまで、上記のプロセスを繰り返します。

#比較回数

#計算式:

#配列表にキーワードが n 個ある場合:

検索が失敗した場合は、キーワードを少なくとも 1 回比較し、検索が成功した場合、キーワード比較の最大回数は b です。

注: a、b、n はすべて正の整数です。

アルゴリズムの複雑さ

二分探索の基本的な考え方は、n 個の要素をほぼ等しい 2 つの部分に分割し、a[n/2] を x と比較することです。 x=a[n/2] の場合、x が見つかり、アルゴリズムは終了します。x

時間計算量は while ループの数にすぎません。

合計 n 個の要素があり、

は n、n/2、n/4、....n/2^k と徐々に続きます (残りの要素数は次に操作されます) )、ここで、k はループの数です。

n/2^k>=1

を四捨五入すると、n/2^k=1

が得られます。 k=log2n、(基数 2、n の対数に基づく)

したがって、時間計算量は O(h)=O(log2n)

として表すことができます。以下は次のようになります。二等分 実装の疑似コードを検索します:

BinarySearch(max,min,des)

mid-<(max min)/2

while( min<= max)

mid=(min max)/2

ifmid=des then

returnmid

elseifmid>des then

max=mid-1

else

min=mid 1

return max

ハーフ検索メソッドは、二分探索法 要素間の順序関係を最大限に利用し、分割統治法を採用しており、最悪の場合でも O(log n) で探索を完了することができます。その基本的な考え方は次のとおりです: (配列要素が昇順に配置されていると仮定して) n 個の要素をほぼ同じ数で 2 つの半分に分割し、a[n/2] を取得し、それを探したい x と比較します (x= の場合)。 a[n/ 2] の場合、x が見つかり、アルゴリズムは終了します。x

以上が二分探索アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。