Design-and-analysis-of-algorithms-binary-search
提供：Dev Guides
DAA-バイナリ検索
この章では、分割統治法に基づく別のアルゴリズムについて説明します。
問題文
ソートされた配列に対してバイナリ検索を実行できます。 このアプローチでは、要素が要素のリストに属している場合、要素 x のインデックスが決定されます。 配列がソートされていない場合、線形検索を使用して位置が決定されます。
溶液
このアルゴリズムでは、要素 x' が配列 numbers [] _ に格納されている一連の数値に属しているかどうかを確認します。 ここで、 ' l_ および r は、検索操作を実行するサブアレイの左右のインデックスを表します。
Algorithm: Binary-Search(numbers[], x, l, r)
if l = r then
return l
else
m := ⌊(l + r)/2⌋
if x ≤ numbers[m] then
return Binary-Search(numbers[], x, l, m)
else
return Binary-Search(numbers[], x, m+1, r)分析
線形検索は O（n） 時間で実行されます。 一方、バイナリ検索では O（log n） 時間で結果が生成されます
- T（n）を、 *n 要素の配列の最悪の場合の比較数とします。
したがって、
T（n）= \ begin \ {cases} 0＆if \：n = 1 \\ T（\ frac \ {n} \ {2}）+ 1＆その他\ end \ {cases}
この再帰関係$ T（n）= log \：n $を使用します。
したがって、バイナリ検索では$ O（log \：n）$時間を使用します。
例
この例では、要素63を検索します。
