28

在考试中有人问我，二分搜索是否是一种分而治之的算法。我的回答是肯定的，因为你把问题分成更小的子问题，直到你得到你的结果。

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

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

4

17 回答 17

20

这本书

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

说 D&C 算法应该有两个不相交的递归调用。即喜欢快速排序。Binary Search 没有这个，即使它可以递归实现，所以我猜这就是答案。

于 2012-01-13T14:16:54.200 回答
12

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

递归地将问题分解为两个或多个子问题，然后将其组合以给出解决方案

在二分搜索中，仍然只有一个问题是每一步将数据减少一半，因此不需要对结果进行征服（合并）阶段。

于 2012-01-13T12:25:37.670 回答
6

在分而治之的策略中：

1.问题分为几部分；

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

3.然后将每个分区/划分的解决方案组合/合并在一起，以得出整体问题的最终解决方案（这属于征服）

例如，快速排序、合并排序。

基本上，二分搜索算法只是在每次迭代中将其工作空间（大小为 n 的输入（有序）数组）分成两半。因此，它肯定是部署了划分策略，结果，时间复杂度降低到 O(lg n)。所以，这掩盖了它的“划分”部分。

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

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

我知道这有点太长了，但我希望它会有所帮助:)

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

我刚才也意识到这个问题很久以前就发布了！我的错！

于 2016-09-09T15:55:54.097 回答
6

它不是。

为了补充@Kenci 的帖子，DnC 算法有一些通用/通用属性；他们：

  1. 将原始问题实例划分为一组更小的自身子实例；
  2. 独立解决每个子实例；
  3. 结合较小/独立的子实例解决方案，为较大/原始实例构建单一解决方案

二分搜索的问题在于，它甚至没有真正生成一组要解决的独立子实例，如步骤 1 所示；它只会通过永久丢弃它不感兴趣的部分来简化原始问题。换句话说，它只会减少问题的大小，而且已经达到了它所能达到的程度。

DnC 算法不仅应该相互独立地识别/解决原始问题的较小子实例，而且还应该使用该组部分独立的解决方案来“构建”整个较大问题实例的单个解决方案.

《算法基础》一书，G. Brassard，P. Bratley说：

它可能是分治法最简单的应用，事实上如此简单，严格来说这是简化而不是分治法的应用：任何足够大的实例的解决方案都简化为单个较小实例的解决方案, 在这种情况下是一半大小。

第226 页的第7.3 节二分搜索。

于 2017-09-08T05:43:57.403 回答
3

显然，有些人认为二进制搜索是一种分而治之的算法，而有些人则不是。我很快搜索了三个参考文献（似乎都与学术界有关），它们称之为 D&C 算法： http ://www.cs.berkeley.edu/~vazirani/algorithms/chap2.pdf http://homepages.ius.edu/rwisman /C455/html/notes/Chapter2/DivConq.htm http://www.csc.liv.ac.uk/~ped/teachadmin/algor/d_and_c.html

我认为 D&C 算法应该至少具有这三个阶段的前两个阶段是普遍的共识：

  • 划分，即决定如何将整个问题分成子问题；
  • 征服，即独立解决每个子问题；
  • [可选地] 合并，即将独立计算的结果合并在一起。

第二阶段 - 征服 - 应该递归地应用相同的技术来解决子问题，方法是分成更小的子子问题等等。然而，在实践中，通常使用一些阈值来限制递归方法，如小尺寸不同的方法可能会更快。例如，当要排序的数组部分的大小变小时，快速排序实现通常使用冒泡排序。

第三阶段可能是空操作，在我看来，它不会取消算法作为 D&C 的资格。一个常见的例子是一个循环的递归分解，for其中所有迭代都纯粹使用独立的数据项（即没有任何形式的减少）。乍一看它可能看起来没什么用，但实际上它是一种非常强大的方式，例如并行执行循环，并被 Cilk 和 Intel 的 TBB 等框架使用。

回到最初的问题：让我们考虑一些实现算法的代码（我使用 C++；抱歉，如果这不是您喜欢的语言）：

int search( int value, int* a, int begin, int end ) {
  // end is one past the last element, i.e. [begin, end) is a half-open interval.
  if (begin < end)
  {
    int m = (begin+end)/2;
    if (value==a[m])
      return m;
    else if (value<a[m])
      return search(value, a, begin, m);
    else
      return search(value, a, m+1, end);
  }
  else // begin>=end, i.e. no valid array to search
    return -1;
}

这里是划分部分int m = (begin+end)/2;，其余部分是征服部分。该算法以递归 D&C 形式显式编写，即使只采用其中一个分支。但是，它也可以写成循环形式：

int search( int value, int* a, int size ) {
  int begin=0, end=size;
  while( begin<end ) {
    int m = (begin+end)/2;
    if (value==a[m])
      return m;
    else if (value<a[m])
      end = m;
    else
      begin = m+1;
  }
  return -1;
}

我认为用循环实现二分查找是很常见的方法；我特意使用了与递归示例中相同的变量名，以便更容易看到共性。因此我们可以再次说，计算中点是除法部分，而循环体的其余部分是征服部分。

但是当然，如​​果你的考官有不同的想法，可能很难让他们相信这是 D&C。

更新：刚刚想到如果我要开发 D&C 算法的通用骨架实现，我肯定会使用二分搜索作为 API 适用性测试之一，以检查 API 是否足够强大，同时也简洁。当然这并不能证明什么:)

于 2012-01-13T16:17:18.290 回答
2

分割部分当然是将集合分成两半。

征服部分正在确定处理部分中是否以及在哪个位置存在搜索元素。

于 2012-01-13T12:24:27.497 回答
2

二分搜索很难用分而治之来描述，因为征服步骤并不明确。算法的结果是大海捞针的索引，纯 D&C 实现将返回针在最小的大海捞针中的索引（0在单元素列表中），然后递归地添加更大的大海捞针中的偏移量在除法步骤中进行了划分。

伪代码解释：

function binary_search has arguments needle and haystack and returns index
    if haystack has size 1
       return 0
    else 
        divide haystack into upper and lower half
        if needle is smaller than smallest element of upper half
            return 0 + binary_search needle, lower half
        else
            return size of lower half + binary_search needle, upper half

加法（0 +或size of lower half）是征服部分。大多数人通过将索引作为参数提供到更大的列表中来跳过它，因此它通常不容易获得。

于 2012-01-13T12:25:10.337 回答
2

计算机科学中的二分法是指在两个对立的选择之间进行选择，在两个不同的选择之间进行选择。二分法是将一个整体分成两个不重叠的部分，这意味着它是将一个整体分为两个部分的过程。它是将一个整体（或一组）划分为两个部分（子集），即：1. 共同穷尽：一切都必须属于一个部分或另一个，以及 2. 互斥：没有任何东西可以同时属于这两个部分。

分而治之的工作是递归地将一个问题分解为两个或多个相同类型的子问题，直到这些子问题变得简单到可以直接解决。

因此，二分搜索将每次迭代检查的项目数量减半，并确定它是否有机会在该一半中找到“关键”项目，或者如果它能够确定关键不存在，则继续移动到另一半。由于该算法本质上是二分法的，因此二进制搜索将认为“密钥”必须在一个部分中，直到它达到退出条件，返回密钥丢失。

于 2012-09-20T07:40:53.827 回答
2

分而治之算法基于以下 3 个步骤：

  1. 划分
  2. 征服
  3. 结合

二分搜索问题可以定义为在排序数组 A[n] 中找到 x。根据此信息：

  1. 除法：将 x 与中间进行比较
  2. 征服：在一个子数组中递归。（在这个数组中找到 x）
  3. 结合：没必要。
于 2015-11-21T21:36:20.227 回答
2

Merge Sort和Quick Sort算法使用分而治之技术（因为有 2 个子问题）并Binary Search受到减少和征服（因为有 1 个子问题）。

因此，二分搜索实际上使用的是递减和征服技术，而不是分而治之的技术。

资料来源：https ://www.geeksforgeeks.org/decrease-and-conquer/

于 2019-11-14T15:13:54.657 回答
1

适当的分治算法将需要处理这两个部分。

因此，很多人不会将二分搜索称为分治算法，它确实划分了问题，但丢弃了另一半。

但最有可能的是，你的考官只是想看看你的论点。（好的）考试不是关于事实，而是关于当挑战超出原始材料时你的反应。

所以恕我直言，正确的答案是：

嗯，从技术上讲，它只包含一个分步，但只需要征服原始任务的一半，另一半已经微不足道了。

顺便说一句：QuickSort 有一个很好的变体，称为 QuickSelect，它实际上利用了这种差异来获得平均O(n)中位数搜索算法。它就像 QuickSort - 但只下降到它感兴趣的一半。

于 2012-01-14T16:35:58.943 回答
0

非正式的定义或多或少：将问题分解为小问题。然后解决它们并将它们放在一起（征服）。解决实际上是决定下一步去哪里（左，右，找到元素）。

这里引用维基百科：

“分而治之”这个名称有时也适用于将每个问题简化为仅一个子问题的算法，例如用于在排序列表中查找记录的二进制搜索算法。

这表明，它不是[更新：误读这句话:)] 只是分而治之的一部分。

更新： 这篇文章让我明白了。我很困惑，因为定义说你必须解决每个子问题。但是，如果您知道不必继续搜索，您就解决了子问题。

于 2012-01-13T12:26:11.493 回答
0

二分搜索是一种分而治之的算法：

1）在分治算法中，我们尝试通过解决较小的子问题（Divide part）来解决问题，并使用该解决方案为我们的更大问题（Conquer）构建解决方案。

2）这里我们的问题是在排序后的数组中找到一个元素。我们可以通过解决类似的子问题来解决这个问题。（我们在这里创建子问题是基于正在搜索的元素小于或大于中间元素的决定）。因此，一旦我们知道元素不可能肯定存在于另一半中，我们就会在另一半中解决类似的子问题。

3）这样我们递归。

4）这里的征服部分只是将子问题返回的值返回到递归树的顶部

于 2012-09-17T05:21:48.153 回答
0

我认为这是减少和征服。

这是维基百科的引述。

“已经为单子问题类提出了名称减少和征服”

http://en.wikipedia.org/wiki/Divide_and_conquer_algorithms#Decrease_and_conquer

根据我的理解，“征服”部分是在找到二进制搜索的目标元素时结束的。“减少”部分是减少搜索空间。

于 2014-08-09T19:54:58.113 回答
0

二分搜索和三分搜索算法基于减少和征服技术。因为，您不划分问题，实际上通过除以 2（三元搜索中的 3）来减少问题。

合并排序和快速排序算法可以作为分治技术的例子。您将问题分成两个子问题，并再次使用这些子问题的算法对数组进行排序。但是，您在二进制搜索中丢弃了数组的一半。这意味着您减小数组的大小，而不是除以。

于 2015-04-12T10:49:06.043 回答
0

不，二分搜索不是分而治之。是的，二分搜索是减少和征服。我相信分而治之算法的效率为 O(n log(n))，而减少和征服算法的效率为 O(log(n))。不同之处在于您是否需要评估数据拆分的两个部分。

于 2015-05-26T15:34:08.990 回答
0

二分搜索是一种减少和征服的算法，而不是分而治之的算法。

二分搜索是一种减少和征服算法，其中子问题大约是原始大小的一半，具有悠久的历史。另一种古老的减少和征服算法是欧几里得算法，它通过减少两个数的最大公约数来计算数字到越来越小的等效子问题，可以追溯到公元前几个世纪。

分而治之是解决概念上困难问题的有力工具：它所需要的只是一种将问题分解为子问题、解决琐碎案例并将子问题与原始问题结合起来的方法。类似地，减少和征服只需要将问题简化为单个较小的问题，例如经典的汉诺塔谜题，它将移动高度为 n 的塔减少为移动高度为 n-1 的塔。

参考：链接1和链接2！

于 2021-06-09T07:12:28.460 回答