DAA - Binäre Suche

In diesem Kapitel werden wir einen anderen Algorithmus diskutieren, der auf der Divide and Conquer-Methode basiert.

Problemstellung

Die binäre Suche kann für ein sortiertes Array durchgeführt werden. Bei diesem Ansatz der Index eines Elementsxwird bestimmt, ob das Element zur Liste der Elemente gehört. Wenn das Array unsortiert ist, wird die Position mithilfe der linearen Suche bestimmt.

Lösung

In diesem Algorithmus wollen wir herausfinden, ob Element x gehört zu einer Reihe von Zahlen, die in einem Array gespeichert sind numbers[]. Wol und r stellen den linken und rechten Index eines Unterarrays dar, in dem eine Suchoperation ausgeführt werden soll.

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)

Analyse

Die lineare Suche läuft in O(n)Zeit. Während die binäre Suche das Ergebnis in erzeugtO(log n) Zeit

Lassen T(n) sei die Anzahl der Vergleiche im schlimmsten Fall in einem Array von n Elemente.

Daher,

$$ T (n) = \ begin {Fälle} 0 & if \: n = 1 \\ T (\ frac {n} {2}) + 1 & andernfalls \ end {Fälle} $$

Verwenden dieser Wiederholungsrelation $ T (n) = log \: n $.

Daher verwendet die binäre Suche $ O (log \: n) $ time.

Beispiel

In diesem Beispiel suchen wir das Element 63.