## Why is Binary Search a divide and conquer algorithm?

13

6

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?

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

10

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.

This answer also adds more details regarding common properties of DnC algorithms, which binary search does not really posses. – code_dredd – 2017-09-09T04:06:53.943

8

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.

"Conquer == merge" is an oversimplification, but still: "reducing the data by half" can be e.g. seen as "merge this half (a set of 0 results) with that other half". – Piskvor – 2012-01-13T12:32:08.463

2With this definition you could still argue it: you "divide" into two sub-problems, one of which definitely does not contain the target (and so is solved trivially without further work), and the other of which might. Then "combine" the fact that it isn't in one, with the answer to whether or not it's in the other. Which to me indicates that turning this into an exam topic is pretty futile. It's not important who thinks binary search can be labelled "divide & conquer", and who thinks it shouldn't, because there's no formal definition of D&C and no results that apply iff an algorithm is D&C. – Steve Jessop – 2012-01-13T12:44:16.443

1... although on second thoughts, I suppose that if you define that the "conquer" must do non-trivial work with two non-trivial solutions, then a D&C algorithm by definition is not singly-recursive and not tail recursive. Those are significant properties, and I think imply for example that a D&C algorithm uses more than O(1) additional space. – Steve Jessop – 2012-01-13T12:49:28.643

Read this: http://www.csc.liv.ac.uk/~ped/teachadmin/algor/d_and_c.html I argued like you: "you have to solve every subproblem". But it's wrong.. the merging phase is combing the two sub problems into one and the result is the found element.

– duedl0r – 2012-01-13T13:01:29.500

Agree with your points, but I still rather keep divide and conquer as a technique for parallel processing (which is not usable in binary search case), but cool discussion anyway. – pointer – 2012-01-13T21:03:46.007

3

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!

2

The divide part is of course dividing the set into halves.

The conquer part is determining whether and on what position in the processed part there is a searched element.

3I disagree. It's a divide-only algorithm. There is no processing happening at all on one half. – Anony-Mousse – 2012-01-14T16:31:07.657

2

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

What do you think about Weiss saying that a traditional D&C algorithm needs two disjoint recursions? – Kenci – 2012-01-13T23:07:08.233

Well, since the notion of a D&C algorithm is rather informal (at least I am not aware of a single commonly accepted formal definition), there is space for interpretation, and so Weiss is in his right to interpret that way. – Alexey Kukanov – 2012-01-14T09:43:03.873

I would say that conquering without ever looking into the other half---because you know the answer can not be there---is the ultimate for of conquest. – Raphael – 2012-01-17T06:43:11.400

2"D&C" is informal to the point where I don't think you can even say necessarily that it consists of two steps "divide" and "conquer". "Conquer" is not some jargon term that means "solve", and has been combined with "divide" to give this expression. In fact "divide and conquer" is an English idiom from the Latin maxim Divide et impera. A more literal translation is "divide and rule", also idiomatic English. The idiom means "I can win by dividing the problem (or victims)", not "first I will perform the 'divide' step, then I will perform the 'conquer' step, and by this means I will win". – Steve Jessop – 2012-01-17T09:27:31.000

1

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.

1

In addition to @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.

1

Binary search is tricky to describe with divide-and-conquer because the conquering step is not explicit. The result of the algorithm is the index of the needle in the haystack, and a pure D&C implementation would return the index of the needle in the smallest haystack (`0` in the one-element list) and then recursively add the offsets in the larger haystacks that were divided in the divison step.

Pseudocode to explain:

``````function binary_search has arguments needle and haystack and returns index
if haystack has size 1
return 0
else
divide haystack into upper and lower half
if needle is smaller than smallest element of upper half
return 0 + binary_search needle, lower half
else
return size of lower half + binary_search needle, upper half
``````

The addition (`0 +` or `size of lower half`) is the conquer part. Most people skip it by providing indices into a larger list as arguments, and thus it is often not readily available.

1

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.

0

The Binary Search is a divide and conquer algorithm:

1) In Divide and Conquer algorithms, we try to solve a problem by solving a smaller sub problem (Divide part) and use the solution to build the solution for our bigger problem(Conquer).

2) Here our problem is to find an element in the sorted array. We can solve this by solving a similar sub problem. (We are creating sub problems here based on a decision that the element being searched is smaller or bigger than the middle element). Thus once we know that the element can not exist surely in one half, we solve a similar sub-problem in the the other half.

3) This way we recurse.

4) The conquer part here is just returning the value returned by the sub problem to the top the recursive tree

0

Dichotomic in computer science refers to choosing between two antithetical choices, between two distinct alternatives. A dichotomy is any splitting of a whole into exactly two non-overlapping parts, meaning it is a procedure in which a whole is divided into two parts. It is a partition of a whole (or a set) into two parts (subsets) that are: 1. Jointly Exhaustive: everything must belong to one part or the other, and 2. Mutually Exclusive: nothing can belong simultaneously to both parts.

Divide and conquer works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly.

So the binary search halves the number of items to check with each iteration and determines if it has a chance of locating the "key" item in that half or moving on to the other half if it is able to determine keys absence. As the algorithm is dichotomic in nature so the binary search will believe that the "key" has to be in one part until it reaches the exit condition where it returns that the key is missing.

0

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.

0

Binary Search and Ternary Search Algorithms are based on Decrease and Conquer technique. Because, you do not divide the problem, you actually decrease the problem by dividing by 2(3 in ternary search).

Merge Sort and Quick Sort Algorithms can be given as examples of Divide and Conquer technique. You divide the problem into two subproblems and use the algorithm for these subproblems again to sort an array. But, you discard the half of array in binary search. It means you DECREASE the size of array, not divide.

0

No, binary search is not divide and conquer. Yes, binary search is decrease and conquer. I believe divide and conquer algorithms have an efficiency of O(n log(n)) while decrease and conquer algorithms have an efficiency of O(log(n)). The difference being whether or not you need to evaluate both parts of the split in data or not.

I've edited your post to remove some chatty text. You could comment on your own answer with what I removed if you still wanted to share. Thanks! – CubeJockey – 2015-05-26T15:57:13.627

0

The informal definition is more or less: Divide the problem into small problems. Then solve them and put them together (conquer). Solving is in fact deciding where to go next (left, right, element found).

Here a quote from wikipedia:

The name "divide and conquer" is sometimes applied also to algorithms that reduce each problem to only one subproblem, such as the binary search algorithm for finding a record in a sorted list.

This states, it's NOT [update: misread this phrase:)] only one part of divide and conquer.

Update: This article made it clear for me. I was confused since the definition says you have to solve every sub problem. But you solved the sub problem if you know you don't have to keep on searching..

http://en.wikipedia.org/wiki/Binary_search_algorithm . It says: A binary search is a dichotomic divide and conquer search algorithm. – Kenci – 2012-01-13T12:33:15.613

Also, QuickSort works in-place, so it doesnt actually go back and put all the puzzles together. – Kenci – 2012-01-13T12:35:07.797

1@Kenci: wikipedia flatly contradicts itself there. The "Binary search algorithm" pages says that it's D&C, whereas the D&C page your quote links to, says that D&C by definition involves multiple recursion, which binary search does not. That's what you get for using thousands of inconsistent editors, your examiners will not agree with all of them ;-) – Steve Jessop – 2012-01-13T12:58:34.577

@SteveJessop But it could be implemented so that it recursively searches the subrange dictated by the comparison ? – Kenci – 2012-01-13T13:10:22.703

@Kenci: of course, but it would only be singly recursive. There's no point also recursing on the half that definitely doesn't contain the target. I assume that your examiners go with the definition on the D&C page, or something similar, that if an algorithm doesn't require "multi-branched" recursion then it's not D&C. – Steve Jessop – 2012-01-13T13:14:29.790

@SteveJessop I just had a look at the textbook (which i probably should have done before asking the question) - Data Structures and Algorithm Analysis in Java, 2nd edtition, Mark Allen Weiss - , and it says that routines in which the text contains at least two recursive calls are called D&C algorithms, while routines who only contain one recursive call are not. Post an answer please. – Kenci – 2012-01-13T13:38:27.963

@Kenci: you found the textbook reference, you may as well answer your own question with the details :-) – Steve Jessop – 2012-01-13T13:41:33.043