CODEWITHSUNDEEP
algorithm
Vladimir007
Vladimir007

Reputation: 1

Divide and Conquer approach

My doubt is that does the recursive binary search algorithm follows Divide and Conquer paradigm. In my opinion, It does not follow. there is no combine step in this algorithm. Please correct me if I am wrong.

The below pseudocode of Recursive Binary Search:

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);
}

Upvotes: 0

Views: 310

Answers (1)

user2736738
user2736738

Reputation: 30926

Yes it is a divide and conquer approach and yes here there is no combine step.

So to be clear, you know that there will be 3 steps :-

  1. Divide. (selecting the appropriate half)
  2. Conquer. (searching that selected half)
  3. Combine. (Doing nothing here)

Time complexity

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

Which tells us that T(n)=O(logn)

The algorithm would take atmost logn steps to stop. On every iteration range is divided by 2.

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

n/2k=1 so k=log2_n

Upvotes: 1

Related Questions