Why is Binary Search a divide and conquer algorith

Question

I was asked if a Binary Search is a divide and conquer algorithm at an exam. My answer was yes, because you divided the problem into smaller subproblems, until you reached your result.

But the examinators asked where the conquer part in it was, which I was unable to answer. They also disapproved that it actually was a divide and conquer algorithm.

But everywhere I go on the web, it says that it is, so I would like to know why, and where the conquer part of it is?

Answer 1

It isn't.

To complement @Kenci's post, DnC algorithms have a few general/common properties; they:

1. divide the original problem instance into a set of smaller sub-instances of itself;
2. independently solve each sub-instance;
3. combine smaller/independent sub-instance solutions to build a single solution for the larger/original instance

The problem with Binary Search is that it does not really even generate a set of independent sub-instances to be solved, as per step 1; it only simplifies the original problem by permanently discarding sections it's not interested in. In other words, it only reduces the problem's size and that's as far as it ever goes.

A DnC algorithm is supposed to not only identify/solve the smaller sub-instances of the original problem independently of each other, but also use that set of partial independent solutions to "build up" a single solution for the larger problem instance as a whole.

The book Fundamentals of Algorithmics, G. Brassard, P. Bratley says the following (bold my emphasis, italics in original):

It is probably the simplest application of divide-and-conquer, so simple in fact that strictly speaking this is an application of simplification rather than divide-and-conquer: the solution to any sufficiently large instance is reduced to that of a single smaller one, in this case of half size.

Section 7.3 Binary Search on p.226.

Answer 2

The book

Data Structures and Algorithm Analysis in Java, 2nd edtition, Mark Allen Weiss

Says that a D&C algorithm should have two disjoint recursive calls. I.e like QuickSort. Binary Search does not have this, even if it can be implemented recursively, so I guess this is the answer.

Answer 3

Apparently some people consider binary search a divide-and-conquer algorithm, and some are not. I quickly googled three references (all seem related to academia) that call it a D&C algorithm: http://www.cs.berkeley.edu/~vazirani/algorithms/chap2.pdf http://homepages.ius.edu/rwisman/C455/html/notes/Chapter2/DivConq.htm http://www.csc.liv.ac.uk/~ped/teachadmin/algor/d_and_c.html

I think it's common agreement that a D&C algorithm should have at least the first two phases of these three:

• divide, i.e. decide how the whole problem is separated into sub-problems;
• conquer, i.e. solve each of the sub-problems independently;
• [optionally] combine, i.e. merge the results of independent computations together.

The second phase - conquer - should recursively apply the same technique to solve the subproblem by dividing into even smaller sub-sub-problems, and etc. In practice, however, often some threshold is used to limit the recursive approach, as for small size problems a different approach might be faster. For example, quick sort implementations often use e.g. bubble sort when the size of an array portion to sort becomes small.

The third phase might be a no-op, and in my opinion it does not disqualify an algorithm as D&C. A common example is recursive decomposition of a for-loop with all iterations working purely with independent data items (i.e. no reduction of any form). It might look useless at glance, but in fact it's very powerful way to e.g. execute the loop in parallel, and utilized by such frameworks as Cilk and Intel's TBB.

Returning to the original question: let's consider some code that implements the algorithm (I use C++; sorry if this is not the language you are comfortable with):

int search( int value, int* a, int begin, int end ) {
  // end is one past the last element, i.e. [begin, end) is a half-open interval.
  if (begin < end)
  {
    int m = (begin+end)/2;
    if (value==a[m])
      return m;
    else if (value<a[m])
      return search(value, a, begin, m);
    else
      return search(value, a, m+1, end);
  }
  else // begin>=end, i.e. no valid array to search
    return -1;
}

Here the divide part is int m = (begin+end)/2; and all the rest is the conquer part. The algorithm is explicitly written in a recursive D&C form, even though only one of the branches is taken. However, it can also be written in a loop form:

int search( int value, int* a, int size ) {
  int begin=0, end=size;
  while( begin<end ) {
    int m = (begin+end)/2;
    if (value==a[m])
      return m;
    else if (value<a[m])
      end = m;
    else
      begin = m+1;
  }
  return -1;
}

I think it's quite a common way to implement binary search with a loop; I deliberately used the same variable names as in the recursive example, so that commonality is easier to see. Therefore we might say that, again, calculating the midpoint is the divide part, and the rest of the loop body is the conquer part.

But of course if your examiners think differently, it might be hard to convince them it's D&C.

Update: just had a thought that if I were to develop a generic skeleton implementation of a D&C algorithm, I would certainly use binary search as one of API suitability tests to check whether the API is sufficiently powerful while also concise. Of course it does not prove anything :)

Answer 4

Divide and Conquer algorithm is based on 3 step as follows:

1. Divide
2. Conquer
3. Combine

Binary Search problem can be defined as finding x in the sorted array A[n]. According to this information:

1. Divide: compare x with middle
2. Conquer: Recurse in one sub array. (Finding x in this array)
3. Combine: it is not necessary.

Answer 5

A proper divide and conquer algorithm will require both parts to be processed.

Therefore, many people will not call binary-search a divide and conquer algorithm, it does divide the problem, but discards the other half.

But most likely, your examiners just wanted to see how you argue. (Good) exams aren't about the facts, but about how you react when the challenge goes beyond the original material.

So IMHO the proper answer would have been:

Well, technically, it consists only of a divide step, but needs to conquer only half of the original task then, the other half is trivially done already.

BTW: there is a nice variation of QuickSort, called QuickSelect, which actually exploits this difference to obtain an on average O(n) median search algorithm. It's like QuickSort - but descends only into the half it is interested in.

Answer 6

I think it is Decrease and Conquer.

Here is a quote from wikipedia.

"The name decrease and conquer has been proposed instead for the single-subproblem class"

http://en.wikipedia.org/wiki/Divide_and_conquer_algorithms#Decrease_and_conquer

According to my understanding, "Conquer" part is at the end when you find the target element of the Binary search. The "Decrease" part is reducing the search space.