Podejście dziel i podbij - algorytm

Wątpię, czy to rekurencyjne wyszukiwanie binarnealgorytm stosuje paradygmat Divide and Conquer. Moim zdaniem to nie następuje. w tym algorytmie nie ma kroku łączenia. Proszę, popraw mnie jeśli się mylę.

Poniższy pseudokod rekurencyjnego wyszukiwania binarnego:

int search(int
a[], int value, int start, int stop)
{
// Search failed
if (start > stop)
return -1;
// Find midpoint
int mid = (start + stop) / 2;
// Compare midpoint to value
if (value == a[mid]) return mid;
// Reduce input in half!!!
if (value <a[mid])
return search(a, start, mid – 1);
else
return search(a, mid + 1, stop);
}

Odpowiedzi:

Tak, to jest podziel i podbij podejście i tak tutaj jest brak kroku łączenia.

Żeby było jasne, wiesz, że będą 3 kroki: -

1. Podzielić. (wybierając odpowiednią połowę)
2. Podbić. (przeszukiwanie wybranej połowy)
3. Połączyć. (Nic tutaj nie robi)

Złożoność czasu

T (n) = T (n / 2) + theta (1)

Co mówi nam, że T (n) = O (logn)

Algorytm przybrałby wartość atmost logn kroki, aby zatrzymać. W każdym zakresie iteracji jest dzielony przez 2.

n,n/2,n/4... n/2^k=1 (after k step)

n/2k=1 so k=log2_n