当前位置：文江博客话题详情

为什么二分查找是分而治之的算法？

发布于 2024-12-26 23:08:34 字数 164 浏览 2 评论 0 原文

考试时有人问我二分查找是否是分而治之的算法。我的答案是肯定的，因为你把问题分成了更小的子问题，直到得到你的结果。

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

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

梦与时光遇 2025-01-02 23:08:34

书上

Data Structures and Algorithm Analysis in Java (2nd Edition), by Mark Allen Weiss

说：D&C 算法应该有两个不相交的递归调用，就像 QuickSort 那样。

二分查找没有这个，尽管它可以递归实现。

The book:

Data Structures and Algorithm Analysis in Java (2nd Edition), by Mark Allen Weiss

Says that a D&C algorithm should have two disjoint recursive calls, just like QuickSort does.

Binary Search does not have this, even though it can be implemented recursively.

回复收藏 0 原文

流心雨 2025-01-02 23:08:34

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

递归地将问题分解为两个或多个子问题
然后将它们组合起来给出解决方案

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

回复收藏 0 原文

回忆那么伤 2025-01-02 23:08:34

事实并非如此。

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

将原始问题实例划分为一组较小的子实例；
独立求解每个子实例；
组合较小/独立的子实例解决方案来为较大/原始实例构建单个解决方案

二分搜索的问题在于，它不真正生成一组独立的解决方案需要解决的子实例，按照步骤1；它只是通过永久丢弃它不感兴趣的部分来简化原始问题。换句话说，它只会减小问题的规模，而且也仅限于此。

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

G. Brassard、P. Bratley 的算法基础一书说道：

这可能是分而治之最简单的应用，事实上非常简单，严格来说，这是一个简化应用，而不是分而治之 ：任何足够大的实例的解决方案都会减少为单个较小实例的解决方案，在本例中为一半大小。

第 226 页上的7.3 二分查找部分。

回复收藏 0 原文

望喜 2025-01-02 23:08:34

在分而治之的策略中：

1.问题被分成几个部分；

2.通过应用手头的算法来独立地攻击/解决这些部分中的每一个（大多数递归用于此目的）；

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

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

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

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

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

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

你也可以从以下地方得到一些想法： https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/running-time-of-binary-search

我现在也意识到这个问题很久以前就发布了！
我的坏！

回复收藏 0 原文

我不在是我 2025-01-02 23:08:34

合并排序和快速排序算法使用分而治之技术（因为有2个子问题）和二分搜索< /code> 属于减少和征服（因为有 1 个子问题）。

因此，二分查找实际上使用的是减少和征服技术，而不是分而治之技术。

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

回复收藏 0 原文

关于从前 2025-01-02 23:08:34

显然，有些人认为二分搜索是一种分而治之的算法，而有些人则不然。我很快用谷歌搜索了三篇参考文献（似乎都与学术界有关），将其称为 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 和英特尔的 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 是否足够强大且简洁。当然这并不能证明什么:)

Apparently some people consider binary search a divide-and-conquer algorithm, and some are not. I quickly googled three references (all seem related to academia) that call it a D&C algorithm:
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

I think it's common agreement that a D&C algorithm should have at least the first two phases of these three:

divide, i.e. decide how the whole problem is separated into sub-problems;
conquer, i.e. solve each of the sub-problems independently;
[optionally] combine, i.e. merge the results of independent computations together.

The second phase - conquer - should recursively apply the same technique to solve the subproblem by dividing into even smaller sub-sub-problems, and etc. In practice, however, often some threshold is used to limit the recursive approach, as for small size problems a different approach might be faster. For example, quick sort implementations often use e.g. bubble sort when the size of an array portion to sort becomes small.

The third phase might be a no-op, and in my opinion it does not disqualify an algorithm as D&C. A common example is recursive decomposition of a for-loop with all iterations working purely with independent data items (i.e. no reduction of any form). It might look useless at glance, but in fact it's very powerful way to e.g. execute the loop in parallel, and utilized by such frameworks as Cilk and Intel's TBB.

Returning to the original question: let's consider some code that implements the algorithm (I use C++; sorry if this is not the language you are comfortable with):

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;
}

Here the divide part is int m = (begin+end)/2; and all the rest is the conquer part. The algorithm is explicitly written in a recursive D&C form, even though only one of the branches is taken. However, it can also be written in a loop form:

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;
}

I think it's quite a common way to implement binary search with a loop; I deliberately used the same variable names as in the recursive example, so that commonality is easier to see. Therefore we might say that, again, calculating the midpoint is the divide part, and the rest of the loop body is the conquer part.

But of course if your examiners think differently, it might be hard to convince them it's D&C.

Update: just had a thought that if I were to develop a generic skeleton implementation of a D&C algorithm, I would certainly use binary search as one of API suitability tests to check whether the API is sufficiently powerful while also concise. Of course it does not prove anything :)

回复收藏 0 原文

煮茶煮酒煮时光 2025-01-02 23:08:34

二分查找很难用分而治之的方法来描述，因为征服步骤并不明确。算法的结果是针在干草堆中的索引，纯 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 + 或 下半部分的大小）是征服部分。大多数人通过提供更大列表中的索引作为参数来跳过它，因此它通常不容易获得。

Binary search is tricky to describe with divide-and-conquer because the conquering step is not explicit. The result of the algorithm is the index of the needle in the haystack, and a pure D&C implementation would return the index of the needle in the smallest haystack (0 in the one-element list) and then recursively add the offsets in the larger haystacks that were divided in the divison step.

Pseudocode to explain:

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

The addition (0 + or size of lower half) is the conquer part. Most people skip it by providing indices into a larger list as arguments, and thus it is often not readily available.

回复收藏 0 原文

梦里泪两行 2025-01-02 23:08:34

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

征服部分是确定处理部分中是否存在搜索元素以及在处理部分的什么位置存在搜索元素。

回复收藏 0 原文

自此以后，行同陌路 2025-01-02 23:08:34

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

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

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