Why is Binary Search a divide and conquer algorithm?

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.

In a divide and conquer strategy :

1.Problem is divided into parts;

2.Each of these parts is attacked/solved independently, by applying the algorithm at hand (mostly recursion is used for this purpose) ;

3.And then the solutions of each partition/division and combined/merged together to arrive at the final solution to the problem as a whole (this comes under conquer)

Example, Quick sort, merge sort.

Basically, the binary search algorithm just divides its work space(input (ordered) array of size n) into half in each iteration. Therefore it is definitely deploying the divide strategy and as a result, the time complexity reduces down to O(lg n).So,this covers up the "divide" part of it.

As can be noticed, the final solution is obtained from the last comparison made, that is, when we are left with only one element for comparison. Binary search does not merge or combine solution.

In short, binary search divides the size of the problem (on which it has to work) into halves but doesn't find the solution in bits and pieces and hence no need of merging the solution occurs!

I know it's a bit too lengthy but i hope it helps :)

Also you can get some idea from : https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/running-time-of-binary-search

Also i realised just now that this question was posted long back! My bad!

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.

I think it is not divide and conquer, see first paragraph in http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm

recursively breaking down a problem into two or more sub-problems which are then combined to give a solution

In binary search there is still only one problem which does just reducing data by half every step, so no conquer (merging) phase of the results is needed.