0

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);
}
Kaushik NP
  • 6,733
  • 9
  • 31
  • 60
Vladimir007
  • 1
  • 3
  • It is not always necessary that Divide and Conquer method will also combine the results. – Anshuman Oct 29 '17 at 05:04
  • Why? if there is no combine step, then, how would you compute the time complexity of this recursive function? – Vladimir007 Oct 29 '17 at 05:47
  • Binary Search is divide and conquer method of searching specific element, whose complexity is known, O(log n). And it doesn't combine. https://stackoverflow.com/a/8851907 – Anshuman Oct 29 '17 at 11:09
  • So the Combine step doesn't do anything but return the result of the recursive call. Nothing says that the Combine step has to do actual work. – Jim Mischel Oct 29 '17 at 16:40

1 Answers1

1

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
user2736738
  • 30,591
  • 5
  • 42
  • 56