Ile porównań dokona wyszukiwanie binarne w najgorszym przypadku przy użyciu tego algorytmu?

Question

Cześć poniżej jest kod binarny dla mojego pseudo realizacji wyszukiwania:

Input: (A[0...n-1], K) 
begin 
    l ← 0; r ← n-1 
    while l ≤ r do 
     m ← floor((l+r)/2) 
     if K > A[m] then l ← m+1 
     else if K < A[m] then r ← m-1 else return m 
     end if 
    end while 
    return -1 // key not found 
end 

Właśnie zastanawiałem się, jak obliczyć liczbę porównań ta implementacja stałaby w najgorszym przypadku na posortowanej tablicy o rozmiarze n?

Czy liczba porównań = lg n + 1? czy coś innego?

Answer 1

Najgorszy przypadek jest w tym przypadku, jeśli element K nie występuje w A i mniejszy niż wszystkich elementów A. Następnie mamy dwa porównań na każdym kroku: K > A[m] i K < A[m].

W każdym kroku tablica jest dzielona na dwie części, każda o rozmiarze (n-1)/2, mamy maksymalnie log_2(n-1) kroków.

To prowadzi do łącznej liczby porównań 2*log_2(n-1), które w rzeczywistości są asymptotycznie równe O(log(n)).

Answer 2

Według strony wikipedia pod adresem binary search, najgorszym rozwiązaniem tego algorytmu jest O(lg n), który mierzy asymptotyczną liczbę potrzebnych porównań. Liczba najgorszych możliwych porównań wynosi , jak wskazano w odpowiedzi @ hielsnoppe.

pseudokod w pytaniu reprezentuje typową realizację poszukiwań binarnych, tak oczekiwane złożoność skuteczności trzymać na tablicy (lub wektor) wielkości n:

• Najlepsza wydajność przypadek: O(1)
• Średnia sprawa wydajność: O(lg n)
• Najgorszy przypadek wydajność: O(lg n)

Przy bliższym zbadaniu, istnieją dwa problemy z Pseudokod w pytaniu:

• Linia: if K > A[m] then return l ← m+1 powinien przeczytać if K > A[m] then l ← m+1. Nie możesz jeszcze wrócić.
• Linia: m ← floor((l+r)/2) może spowodować przepełnienie, jeśli liczby są wystarczająco duże, gdy pracujesz z liczbami całkowitymi o stałej wielkości. Prawidłowa składnia różni się w zależności od używanego języka programowania, ale w tym przypadku problem zostanie rozwiązany: m ← (l + r) >>> 1, gdzie , gdzie jest operatorem przesuniętym w prawo bez znaku. Przeczytaj więcej o problemie w here.

Answer 3

bardzo niewielkiej korekty hielsnoppe's answer:

W n -elementowe tablicy (n > 0), przy czym element do porównania jest indeksem m = floor((n-1)/2). Tak więc istnieją trzy możliwości

1. A[m] < K, a następnie po jednym porównania, wyszukiwanie jest kontynuowane w n-1-m = ceiling((n-1)/2) -elementowe tablicy.
2. A[m] > K, a następnie po dwóch porównaniach wyszukiwanie jest kontynuowane w macierzy -elementach m.
3. A[m] == K, a następnie skończyliśmy po dwóch porównaniach.

Więc jeśli oznaczymy maksymalną (najgorszy przypadek) liczbę porównań do poszukiwania w n -elementowe tablicy przez C(n) mamy

C(0) = 0 
C(n) = max { 1 + C(ceiling((n-1)/2), 2 + C(floor((n-1)/2) }, n > 0 

dla nieparzystych n = 2k+1, podłoga i sufit są identyczne, więc maksymalna jest oczywiście to drugie,

C(2k+1) = 2 + C(k) 

i nawet n = 2k znajdujemy

C(2k) = max { 1 + C(k), 2 + C(k-1) }. 

Dla n = 2, że postanawia C(2) = 1 + C(1) = 1 + 2 = 3 dla wszystkich większych nawet n maksymalna jest 2 + C(k-1), ponieważ dla n >= 1 mamy C(n) <= C(n+1) <= C(n) + 1.

Oceniając rekursji w ciągu pierwszych kilku n znajdujemy

C(0) = 0 
C(1) = 2 
C(2) = 3 
C(3) = C(4) = 4 
C(5) = C(6) = 5 
C(7) = C(8) = C(9) = C(10) = 6 
C(11) = ... = C(14) = 7 
C(15) = ... = C(22) = 8 
C(23) = ... = C(30) = 9 

więc przez indukcję dowodzimy

C(n) = 2k, if 2^k <= n+1 < 2k + 2^(k-1), and 
C(n) = 2k+1, if 2^k + 2^(k-1) <= n+1 < 2^(k+1) 

lub

C(n) = 2*log2(n+1) + floor(2*(n+1)/(3*2^floor(log2(n+1)))). 

Jest to dokładna górna granica.