Talk:二分搜尋

重复

该页条目主题与折半搜索算法是一样的，重复了---Qiii2006 (留言)

建議更名：“二分搜尋演算法”→“二分搜尋”

“二分搜尋演算法” → “二分搜尋”：“算法”一词显得多余，“二分查找”已经足以识别主题，并且更简洁。另外，《算法》正文中多称“二分查找”而非“二分查找算法”。--深鸣（留言） 2024年7月26日 (五) 11:47 (UTC)

( ✓ )同意 "二分查找"即可--Uwuw（留言） 2024年7月27日 (六) 21:05 (UTC)

赞同。英文日文条目也是如此。--YFdyh000（留言） 2024年7月27日 (六) 21:54 (UTC)

参考資料

一些想法

先看了序言和算法部分，我是小白，就不在GAN区留言了🤣

• 中间元素有类似中点或中位数那种感觉的链接吗？我的第一感觉是[1, 2, 3, 5, 7, 11, 13]里面的3、5、7都算中间元素🤣 「正中间」好像又不适用于偶数的情况？

  《算法导论》里面写的是「序列中点」，《算法》里的用词是「中间键」🤣。一般都是把$m$取成中间元素，但把它加一减一对算法实现都没有影响，所以其实都可以算作中间元素。--深鸣（留言） 2025年5月10日 (六) 04:15 (UTC)

• 「包括哈希表在内的某些数据结构，在搜索效率上可能超过二分查找，但二分查找还可用于查找最接近目标值的上界或下界，即使目标值不在数组中」 — 这里用了「但」，我感觉「二分查找在搜索效率上不及哈希表……」会自然点。

  我改成了二分查找的搜索效率可能不及哈希表等数据结构，但其还可用于查找最接近目标值的上界或下界。--深鸣（留言） 2025年5月10日 (六) 04:15 (UTC)

• 「则在数组较小的那一半中继续查找」 — 「数组中较小的那一半元素/值」，中心语可以省略吗？

  数组较小/较大的那一半，中心语应该是数组？在某一半数组中继续查找，我觉得好像没问题？《算法》里用的是「左/右子数组」的说法，但是原数组可能不一定是升序排列的，我觉得可能不太妥当。--深鸣（留言） 2025年5月10日 (六) 04:15 (UTC)

  想了想，python有[1, 2, 3] < [4, 5, 6]（较小的数组），然后可以1 in [1, 2, 3]（在数组中查找），好像是没有问题？--For Each element In group ... Next 2025年5月10日 (六) 06:25 (UTC) 😄1

• 「如此所做，若目标值在数组中出现多次，结果可能会有所不同」 — 指的是floor和ceil返回的结果不一样，比如[1, 2, 2, 2, 2, 3]，分别扔出来2和3？我还以为是看人品，1到4都有可能出来，拿python改完试了半天，每次跑的结果都一样🤣

  这里确实是说floor和ceil返回的结果不一样，即$m$取$\lfloor {\frac {L+R}{2}}\rfloor$和$\lceil {\frac {L+R}{2}}\rceil$的返回值可能不一样。如果代码里没有随机数之类的话，每次跑的结果应该是一样的，毕竟每一步的执行结果都是确定的。--深鸣（留言） 2025年5月10日 (六) 04:15 (UTC)

• 「替代过程」 — 其他过程/另一过程/第二过程是不是好一点？

  改成了「另一过程」。--深鸣（留言） 2025年5月10日 (六) 04:15 (UTC)

• 「常规过程通常返回第4个元素（索引为3），但并不总是返回第一个重复项」 — 这个「通常」感觉比较奇怪：
  • 如果有8个元素，且x[3]和x[4]都是目标值，只能说对binary_search而言索引3是C位🤣 但x[3]和x[4]也不一定是通常情况，如果目标值出现在索引0、1、2的位置上，肯定是不会返回第4个元素的。
  • 而如果给定[1, 2, 3, 4, 4, 5, 6, 7]，那好像所有时候都是返回位置3，应该没有「不通常」状况？
  • 感觉就是binary_search偶数项目时C位靠左，binary_search_alternative以右为尊，本来和「第一个重复项」也没什么关系？

  我改成了常规过程会返回第4个元素（索引为3），但其并非总是首个重复项，估计好一点。「通常」当时是想说「多数常规过程」，下面库支持里不少编程语言的标准库里的算法应该都能算常规过程，但不知道是怎么实现的，跑出来的结果或许会不一样。这里其实主要想引出下面的查找最左/右侧元素的内容。binary_search和binary_search_alternative的本质区别应该不是这个，靠左和靠右是看m向上取整还是向下取整🤣。两个函数m的取值不太一样，主要是想说m向上取整还是向下取整都行（原论文用的是ALGOL，所以也是向下取整）。--深鸣（留言） 2025年5月10日 (六) 04:15 (UTC)

  感觉用[1,2,3,4,4,4,4,5,6,7]举例会比较好。返回3到6都是ok的，上面两个例子是返回第5个或第6个元素。而不同的库实现结果未必一样，也不必然和最左/最右有关系🤣--For Each element In group ... Next 2025年5月10日 (六) 06:50 (UTC)

  改了一下，估计没问题了。--深鸣（留言） 2025年5月10日 (六) 07:48 (UTC)

• 为什么上面定义函数用了is，而重复元素那一节定义函数用了冒号（我说改python总觉得少干了什么🤣）

  伪代码太熟悉，所以跳过没看了🤣。--深鸣（留言） 2025年5月10日 (六) 04:15 (UTC)

• 「目标值的最近邻是其前驱或后继之一，取决于哪个位置更接近」 — 我不清楚最近邻这个概念。看右边的图，5和4或7都是位置上「紧贴」的。最近邻是4而不是7，是因为从差值上看，(5-4) < (7-5)吗？

  写的时候全是数组，把数字大小直接想成了位置。我改成了「取决于哪个值更接近」。--深鸣（留言） 2025年5月10日 (六) 04:15 (UTC)

• 「考虑到是否需要将区间的端点包含在内，以及数组中是否包含与端点匹配的元素，其结果可能会相差1」 — 端点加减1这个好理解。「数组中是否包含与端点匹配的元素」和相差1是什么关系，比如[1,1,1,2,3,4]，如果说两个值是1和4，范围查找的结果会是几（还是要说是哪个位置上的1）？

  这里的意思是，端点和是否存在对应元素两个因素，共同决定了要不要微调。例如，数组中本身存在「1」，那么包含元素「1」（≥1）和不包含元素「1」（>1）就有差别；但是如果数组中不存在「1」，那么包含元素「1」（≥1）和不包含元素「1」（>1）就没有差别。我改成了考虑到是否需要将区间的端点包含在内，以及数组中是否包含与端点匹配的元素，左右端点的排名值可能会有调整，不知道怎么表述更加合适🤣。--深鸣（留言） 2025年5月10日 (六) 04:15 (UTC)

  好难🤣--For Each element In group ... Next 2025年5月10日 (六) 06:25 (UTC)

--For Each element In group ... Next 2025年5月9日 (五) 17:34 (UTC) 🤣1

感谢您的意见。其实本来想让您看看这篇条目，毕竟您对这方面也比较了解。但是看到您挂了个半退休模板，并且先前评了篇甲级，应该挺累的，所以就没有邀请--深鸣（留言） 2025年5月10日 (六) 04:15 (UTC)

考二级的时候见过一些名词，比如二叉树。然后什么也没学会，反正总共就三四分，直接坑了。就知道前序遍历选A在中间的那个选项，后序遍历高概率选HGFEDCBA🤣--For Each element In group ... Next 2025年5月10日 (六) 06:25 (UTC) 🤣1

• 题外话，ordered（区分顺序的）和sorted（已排序的）为什么都可以叫「有序」🤣

  个人理解，区分顺序的->有顺序的->有序，已排序的->排好序->有序🤣。如果之于数组而言的话，至少对于C++的std::vector（可以视作C++里对动态数组的标准实现）来说是有顺序的（循序，Sequential），所以「有序数组」就是指后者「sorted」了。--深鸣（留言） 2025年5月10日 (六) 07:43 (UTC)

• 「否则，搜索过程可能会在倒数第二层中止，此时比较了 ⌊log2(n)⌋ 次，比最坏情况少一次」 — 意思是如果画出来是不满的二叉树，就有可能少一次。比如图上的例子把100干掉，然后要比93，然后第二次比较90!=93时就直接终止？

  是的。满的二叉树就是完美二叉树。--深鸣（留言） 2025年5月10日 (六) 07:43 (UTC)

• 后面的公式我看不懂，应该不是目标读者🤣 前面那句「成功搜索的平均情况是搜索数组中每个元素所需迭代次数之和除以元素数量n，失败搜索的平均情况则是搜索数组各区间所需迭代次数之和除以区间数量n+1」我好像还能理解。然后试了下
  • 成功时的次数，按例图来看，第n层元素迭代n次， (1+2+2+3+3+3+3)/7=2.43，好像和下面那个二又七分之三对得上
  • 失败时的次数，比如例图把100踢掉变成6个元素，就有(-inf, 20), (20, 30), (30, 40), (40, 50), (50, 80), (80, 90), (90, +inf)共7个区间。前6种情况要比较三轮，最后一种比较两轮，平均失败要比较(6*3+2)/(6+1)=2.86次？

  是的， 赞。您分明就是目标读者。--深鸣（留言） 2025年5月10日 (六) 07:43 (UTC)

• 「算法的一种实现方法是在搜索结束后检查中间元素是否与目标值相等」 — 「还有一种实现方法是待搜索结束后，再检查中间元素是否与目标值相等」？

  已修改。--深鸣（留言） 2025年5月10日 (六) 07:43 (UTC)

• 「因为即使在最坏情况下，二分查找的比较循环也只执行 ⌊log2(n)+1⌋次，因此除非n极大，否则每次迭代效率的微小提升不足以弥补额外增加的迭代次数」 — 意思从底层上看，迭代的开销远超过比较运算的开销吗？虽然新方法多一次迭代，但如果n不是特别小，比较次数上应该都能赚回来，但是这里用的是「极大」🤣

  在现代流水线里，寄存器间比较只需大约1个周期，并能与取数并行；但是每层循环都要冒一次分支预测失误的风险（失误代价动辄十几个周期，[1]）。为了让总周期差不多，总比较次数可能至少得有十几次，$n=2^{15}$也不是个小数目了🤣。如果是按照脚注d中的时间来看，两种算法的运行时间相等时，需要$n=2^{66}$，太大了🤣。--深鸣（留言） 2025年5月10日 (六) 07:43 (UTC)

• 「例如，与32位无符号整数相比，两个64位无符号整数的比较时间至多是前者最坏情况的两倍，该情况出现在整数完全相同时」 — 「最坏情况」前面都是说二分法提到的极端情况。如果只是两个uint64/uint32比较，这里的「最坏情况」怎么理解。是说比如uint32运算4294967295 == 4294967295比0 == 0的速度不一样，而uint64最慢的比较也不及uint32运算最慢时间的两倍？

  现代ALU比较两个整数都是一个时钟周期解决了，还是补了个假设逐位比较的前提。假设每位比较时间相同，最坏情况就是两个uint32相同，或者是前面位都相同，只有最后比较的那一位不一样，这样逐位比较需要比较32位。两个uint64至多比较64个位，最坏情况也就是前者的两倍。最好情况就是第一位不一样，直接判断不相等后结束。这和前面二分查找的最坏情况没有关系。--深鸣（留言） 2025年5月10日 (六) 07:43 (UTC)

  中文没有先行词，最后那句改成括号「假设逐位比较，与32位无符号整数相比，64位无符号整数的比较时间至多是前者最坏情况（即两个整数相同）的两倍」感觉好理解点。--For Each element In group ... Next 2025年5月10日 (六) 11:46 (UTC)

--For Each element In group ... Next 2025年5月10日 (六) 06:25 (UTC)

• 「在有序数组中，当插入和删除操作与查找操作交替进行时，二分查找的效率会非常低下。每次插入或删除操作的时间复杂度为O(n)。」 — 是二分查找本来速度不错，但有序数组增减元素太慢（后半部分元素要集体搬家?），所以整体效率低下吗？或者说把前置的排序成本也算到里面，二分查找效率不高？
• 线性搜索、二叉树好理解；哈希表我虽然不清楚原理，但知道字典结构比列表结构查找速度快；再后面内容太专业，我就看不懂了
• 历史和实现问题我没有什么疑惑。

感觉我就是只能看懂基本思想，看不懂细节实现的那种🤣 祝评选顺利--For Each element In group ... Next 2025年5月10日 (六) 11:45 (UTC)

这一章节其实主要在讲有序数组与其他方案的比较，偏向查询操作。因为增删查改是针对特定的数据结构来的，二分查找可以看作是对有序数组的查询操作。但对有序数组本身来说，插入和删除操作的效率不高。稍微改了改，应该可以了。

最后感谢阁下的评审。--深鸣（留言） 2025年5月10日 (六) 11:56 (UTC)

新条目推荐讨论

在候选页的投票结果

• 计算机科学家高德纳称，哪种算法的「基本思想相对简单，但其细节却出奇复杂」？

  二分搜尋条目由深鸣（讨论 | 貢獻）提名，其作者为深鸣（讨论 | 貢獻），属于“algorithm”类型，提名于2025年5月7日 12:09 (UTC)。

主编邀请了UjuiUjuMandan君做条目评审，为防止拉票嫌疑而在此说明。--深鸣（留言） 2025年5月9日 (五) 06:18 (UTC)

• • 說明：翻译自英维FA。英维条目还经过了同行评审并发表为论文，故本文的「空间复杂度」虽然没有来源（可能是因为过于基础而没有来源提到），但肯定是没有问题的。--深鸣（留言） 2025年5月7日 (三) 12:09 (UTC)
  • (＋)支持近期大幅擴充（擴充後的內容是原來的三倍以上）的條目。--Wolfch (留言) 2025年5月7日 (三) 15:19 (UTC)
  • (＋)支持--Banyangarden（留言） 2025年5月8日 (四) 02:05 (UTC)
  • (＋)支持--金色黎明（留言） 2025年5月8日 (四) 02:34 (UTC)
  • (＋)支持--Shwangtianyuan 让中国再次伟大 2025年5月8日 (四) 15:11 (UTC)
  • (－)反对部分章节未有来源或来源欠佳，注释里直接用作者+年份的方式引称专著似乎不是恰当的适合维基百科的行文方式，概要文段过于偏向有专业知识者阅读，忽视一般读者未了解相关内容的友好性。--∮♩♪♫♬♭♮♯☧⚧☦︎ 2025年5月8日 (四) 21:23 (UTC)
    • @静魔魔女：注释已经直接修改成了作者名。未有来源的问题请读说明，欠佳的来源请指明。专业性问题，也请指明是哪里看不懂，我认为目前行文与GA戴克斯特拉算法相当，但可能存在知识的诅咒。意见已采纳，您看看还有什么问题吗？--深鸣（留言） 2025年5月9日 (五) 00:24 (UTC)
  • (＋)支持，作为专业入门条目而言目前的版本没有太大的[[[WP:JARGON]]问题。——Mirfaek 2025年5月9日 (五) 05:31 (UTC)
    • @Mirfaek：阁下肯定是看了条目的，没有太大的行话问题，是否可以理解成仍有少量问题？如有可能，还请您不吝指教，谢谢。--深鸣（留言） 2025年5月9日 (五) 06:04 (UTC)
      • 阁下改善条目的热情令人敬佩，主要是我理解起来比较吃力，但毕竟我对计算机科学除了拿R的模块跑点统计分析外完全是一无所知，不能代表大部分读者的计算机科学水平，就不贸然提出意见了。——Mirfaek 2025年5月9日 (五) 06:10 (UTC)
  • (＋)支持--YuCheinSYQ留言 2025年5月9日 (五) 14:17 (UTC)

優良條目評選

二分搜尋（编辑 | 讨论 | 历史 | 链接 | 监视 | 日志），分類：计算机信息 - 资讯科技 - 算法，提名人：深鸣（留言） 2025年5月8日 (四) 06:55 (UTC)

投票期：2025年5月8日 (四) 06:55 (UTC)至2025年5月15日 (四) 06:55 (UTC)
下次可提名時間：2025年6月14日 (六) 06:56 (UTC)起
請記得為當選條目撰寫簡介頁面，如此當選條目才有可能出現在首頁。

主编邀请了UjuiUjuMandan君做条目评审，为防止拉票嫌疑而在此说明。--深鸣（留言） 2025年5月9日 (五) 06:18 (UTC)

• 符合优良条目标准：提名人票。五级基础条目，翻译自英维FA。英维条目还经过了同行评审并发表为论文，故本文的「空间复杂度」虽然没有来源（可能是因为过于基础而没有来源提到），但内容本身肯定是没有问题的。深鸣（留言） 2025年5月8日 (四) 06:55 (UTC)
• 符合优良条目标准 -- Pathfinbird（留言） 2025年5月8日 (四) 08:22 (UTC)
• 符合优良条目标准！符合六项标准。(～)補充：你可以看看OI wiki上有没有相关内容和来源，或者找找你维的OIer评评，他们可能有些可取意见。( π )题外话：作为一个AFOer不会二分搜索真是可耻 囧rz……--KurGenera^(留言) 2025年5月8日 (四) 13:49 (UTC)

  @Kurgenera：我也参加过好几次OI，也算是小半个OIer吧，虽然没得过什么奖就是了🤣。感觉OI wiki上更偏向于具体代码实现以及怎么极致压行和优化，不过刚刚也翻了一下，感觉没什么可以参考的，「位运算代替乘法」之类的编译器优化应该没必要提（倒是可以放到维基学院里面去）。具体实现的话，条目里也有伪代码了，对普通读者来说应该足够。--深鸣（留言） 2025年5月8日 (四) 14:10 (UTC) 🙇‍♂️1

• 符合优良条目标准--Banyangarden（留言） 2025年5月9日 (五) 02:31 (UTC)
• 符合优良条目标准--David Jackson(留言) 2025年5月12日 (一) 07:02 (UTC)
• 符合优良条目标准——𝗠𝗢𝗡𝗘𝗬 2025年5月15日 (四) 05:50 (UTC)
• 符合优良条目标准--🍫巧克力～✿ 2025年5月15日 (四) 06:48 (UTC)

---

符合优良条目标准7张， 不符合优良条目标准0张，无效票0张， 入選優良條目—提斯切里（留言） 2025年5月15日 (四) 07:02 (UTC)