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 :)

4The conquer part is where you solve the problem. I'm not sure why they said it wasn't divide-and-conquer. These are things you should be sure to also ask your examiners! They're the only ones that know the answer they were looking for. – Cody Gray – 2012-01-13T12:23:33.510

Well, you search only in one half. So yes, you divide the problem. But no, you don't conquer both halves, only one (at least when you are smart. ;-)) – Anony-Mousse – 2012-01-14T16:32:03.850

Is it 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

– arun8 – 2014-08-09T19:48:37.203@CodyGray I know I'm late, but please see my answer on why binary search is not really a DnC algorithm. It goes into more detail than the accepted answer regarding the properties that any algorithm needs to have in order to be considered a DnC algorithm.

– code_dredd – 2017-09-09T04:05:38.700