Ken*_*nci 17 algorithm computer-science binary-search divide-and-conquer data-structures
我被问到二元搜索是否是考试中的分而治之算法.我的回答是肯定的,因为你将问题分成了较小的子问题,直到你达到了结果.
但是检查员询问其中的征服部分在哪里,我无法回答.他们也不赞成它实际上是一种分而治之的算法.
但是我到网上的所有地方都说它是,所以我想知道为什么,以及征服它的部分在哪里？
Ken*_*nci 16
这本书
Data Structures and Algorithm Analysis in Java, 2nd edtition, Mark Allen Weiss
说D&C算法应该有两个不相交的递归调用.就像QuickSort.二进制搜索没有这个,即使它可以递归实现,所以我猜这就是答案.
小智 9
我认为这不是分而治之,请参阅http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm中的第一段
递归地将问题分解为两个或更多个子问题,然后将这些子问题组合起来以给出解决方案
在二进制搜索中,仍然只有一个问题是每一步只减少一半的数据,因此不需要征服(合并)阶段的结果.
事实并非如此。
为了补充@Kenci 的帖子，DnC 算法有一些通用/通用属性；他们：
二分搜索的问题在于，它甚至没有真正生成一组要解决的独立子实例，如步骤 1 所示；它只是通过永久丢弃它不感兴趣的部分来简化原始问题。换句话说，它只是减小了问题的大小，并且仅限于此。
DnC 算法不仅应该能够独立地识别/解决原始问题的较小子实例，而且还可以使用这组部分独立的解决方案为整个较大的问题实例“构建”单个解决方案。
G. Brassard、P. Bratley所著的《算法基础》一书说道：
这可能是分而治之最简单的应用，事实上如此简单，严格来说这是一种简化而不是分而治之的应用：任何足够大的实例的解决方案都被简化为单个较小实例的解决方案，在本例中为一半大小。
第 226页第 7.3节二分查找。
小智 6
在分而治之的策略中：
1.问题分为几个部分；
2.通过应用手头的算法（主要是递归用于此目的），这些部分中的每一个都被独立攻击/解决；
3.然后将每个分区/分区的解决方案组合/合并在一起，以得出问题的最终解决方案作为一个整体（这是被征服的）
例如，快速排序、归并排序。
基本上，二分搜索算法只是在每次迭代中将其工作空间（大小为 n 的输入（有序）数组）分成两半。因此，它肯定部署了除法策略，结果，时间复杂度降低到 O(lg n)。因此，这掩盖了它的“除法”部分。
可以看出，最终的解决方案是从最后一次比较中获得的，也就是说，当我们只剩下一个元素进行比较时。二分搜索不合并或组合解决方案。
简而言之，二分搜索将问题的大小（它必须在其上工作）分成两半，但没有找到零碎的解决方案，因此不需要合并解决方案！
我知道这有点太长了，但我希望它有帮助:)
您也可以从以下位置获得一些想法：https : //www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/running-time-of-binary-search
我也刚刚意识到这个问题很久以前就发布了！我的错！