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

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.

Answer 2

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..

Answer 3

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.

Answer 4

The Merge Sort and Quick Sort algorithms use the divide and conquer technique (because there are 2 sub-problems) and Binary Search comes under decrease and conquer (because there is 1 sub-problem).

Therefore, Binary Search actually uses the decrease and conquer technique and not the divide and conquer technique.

Source: https://www.geeksforgeeks.org/decrease-and-conquer/

Answer 5

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.

Answer 6

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!