Divide And Conquer Strategy With Binary Search

Divide and conquer strategy with binary search

Apparently some people consider binary search a divide-and-conquer algorithm, and some are not.

Divide and conquer strategy with binary search

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.pdfhttp://homepages.ius.edu/rwisman/C455/html/notes/Chapter2/DivConq.htmhttp://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.

    Binary Search using Divide and Conquer

    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.

Navigation menu

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.

Divide and conquer strategy with binary search

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 -loop with all iterations working purely with independent data items (i.e. no reduction of any form).

What hecs option is best

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

Here the divide part is and all the rest is the conquer part.

Best tse new ipo 201

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:

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.

Divide and conquer strategy with binary search

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