为什么二进制搜索是一个分而治之的算法？

2018-06-14 01:24:08

我被问到二进制搜索是否是考试中的分而治之算法。我的回答是肯定的，因为你把问题分成了更小的问题，直到你达到你的结果。

但考官们问了这个征服部分在哪里，我无法回答。他们也不赞成它实际上是一个分而治之的算法。

但是，无论在哪里，我都会上网，它说的是，所以我想知道为什么，以及它的征服部分在哪里？

这本书

Data Structures and Algorithm Analysis in Java, 2nd edtition, Mark Allen Weiss

说D＆C算法应该有两个不相交的递归调用。即像QuickSort。二进制搜索没有这个，即使它可以递归实现，所以我想这是答案。

我认为这不是分而治之，请参阅http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm中的第一段

递归地将问题分解成两个或更多的子问题，然后将这些问题结合起来给出一个解决方案

在二分查找中，仍然只有一个问题，即每一步只减少一半数据，因此不需要征服（合并）阶段的结果。

在分治策略中：

1.问题分成几部分;

2.通过应用手边的算法，每个部分都被独立地攻击/解决（主要是递归用于此目的）;

3.然后将每个分区/分区的解决方案组合在一起以整体解决问题（这需要征服）

例子，快速排序，合并排序。

基本上，二进制搜索算法只是在每次迭代中将其工作空间（大小为n的输入（有序）数组）分成一半。因此，它肯定会部署分而治之，因此时间复杂度降低到O（lg n）。因此，这掩盖了“分裂”的一部分。

可以注意到，最后的解决方案是从最后一次比较中获得的，也就是说，当我们只剩下一个元素进行比较时。二进制搜索不合并或合并解决方案。

简而言之，二进制搜索将问题的大小（它必须工作的）分成两半，但没有找到解决方案，因此不需要合并解决方案！

我知道这有点太冗长，但我希望它有助于:)

您也可以从以下网址获得一些建议：https：//www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/running-time-of-binary-search

我也意识到这个问题已经发布很久了！我的错！

链接地址: http://www.djcxy.com/p/40031.html