为什么二进制搜索采用分而治之算法？ [英] 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?

推荐答案

这本书

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

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

Says that a D&C algorithm should have two disjoint recursive calls. I.e like QuickSort. Binary Search does not have this, even if it can be implemented recursively, so I guess this is the answer.

这篇关于为什么二进制搜索采用分而治之算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！