Why is Binary Search a divide and conquer algorithm?
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?
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. Ie like QuickSort. Binary Search does not have this, even if it can be implemented recursively, so I guess this is the answer.
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.
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!
链接地址: http://www.djcxy.com/p/40032.html上一篇: 来自Google的算法访谈
下一篇: 为什么二进制搜索是一个分而治之的算法？