討論:二分搜尋

重複

該頁條目主題與折半搜索算法是一樣的，重複了---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)