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&else \ end {cases} $$
この漸化式を使用すると、$ T(n)= log \:n $になります。
したがって、バイナリ検索は$ O(log \:n)$時間を使用します。
例
この例では、要素63を検索します。