DAA - wyszukiwanie binarne

W tym rozdziale omówimy inny algorytm oparty na metodzie dziel i rządź.

Stwierdzenie problemu

Wyszukiwanie binarne można przeprowadzić na posortowanej tablicy. W tym podejściu indeks elementuxjest określane, czy element należy do listy elementów. Jeśli tablica nie jest posortowana, do określenia pozycji używane jest wyszukiwanie liniowe.

Rozwiązanie

W tym algorytmie chcemy znaleźć, czy element x należy do zbioru liczb przechowywanych w tablicy numbers[]. Gdziel i r reprezentują lewy i prawy indeks tablicy podrzędnej, w której ma zostać przeprowadzona operacja wyszukiwania.

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)

Analiza

Rozpoczyna się wyszukiwanie liniowe O(n)czas. Podczas gdy wyszukiwanie binarne daje wynik w formacieO(log n) czas

Pozwolić T(n) być liczbą porównań w najgorszym przypadku w tablicy n elementy.

W związku z tym,

$$ T (n) = \ begin {cases} 0 & if \: n = 1 \\ T (\ frac {n} {2}) + 1 & w przeciwnym razie \ end {cases} $$

Używając tej relacji powtarzania $ T (n) = log \: n $.

Dlatego wyszukiwanie binarne używa $ O (log \: n) $ czas.

Przykład

W tym przykładzie wyszukamy element 63.