再看二元搜尋法 Binary Search(上)

如果你自認對二元搜尋(binary search, 大陸譯作折半搜索) 夠熟悉了,卻沒讀過 Netty van Gasteren 和 Wim Feijen 的研究筆記 The Binary Search Revisited, 強烈建議你找時間看看。

最近為了今夏的 FLOLAC 研習營開始找些資料。為了教些離開研習營後仍有用的東西,今年我想教 Hoare 邏輯與 Dijkstra 使用最弱前提(weakest precondition) 的程式建構法。對想寫好程式的人來說,這應是基礎知識,但大家對這些題目卻陌生得令人驚訝。

二元搜尋似乎是個該談到的例子:給一個排序好、長度為 N 的陣列,在 O(log N) 的時間內決定其中是否有某個值。資訊系學生在演算法課上一定學過二元搜尋。身經百戰的程式員寫個二元搜尋程式應該也不是難事吧?然而 Jon Bentley 在他有名的 Programming Pearls 一書中卻提到只有大約一成的專業程式員能第一次把這程式寫對。這一定要親身試試看才會相信。我抱著警覺心試了一次,寫了一個應該正確(畢竟我對這套方法算是比較熟了),但不怎麼漂亮的程式。請朋友寫寫看,也果然出現了一些常見的 bug. 看來這確實是個程式設計課堂上該講的好例子。

迴圈、不變量、與界限

Van Gasteren 和 Feijen 在一篇 1995 年的研究筆記中釐清了大家常有的一個迷思:你認為你對二元搜尋很了解嗎?那您可知道,二元搜尋其實並不一定要用在排序好的陣列上?事實上,他們認為總是把二元搜尋類比為翻字典找字,反倒造成了一個教學盲點。

Van Gasteren 和 Feijen 先試解一個更廣的問題:給定整數 MN, 和一個接受兩個整數參數的布林函數 Φ,已知 M < N,並知 Φ(M,N) 成立。Φ 另需滿足一些條件,待會兒再談。試寫一個程式,找兩個介於 MN 之間、滿足 Φ 的相鄰整數。若寫成邏輯式子,程式執行完畢後需滿足:

M ≤ l < N   ∧   Φ(l,l+1)

這是 Van Gasteren 和 Feijen 的程式:

  { M < N ∧ Φ(M,N) }
  l, r := M, N
  { Inv: M ≤ l < r ≤ N  ∧  Φ(l,r),   Bound: r - l }
; do l+1 ≠ r →
    { l + 2 < r }
    m := (l + r) / 2
  ; if Φ(m,r) → l := m
    [] Φ(l,m) → r := m
    fi
  od
  { M ≤ l < N  ∧  Φ(l,l+1) }

這裡的虛擬碼使用的是 Dijkstra 的 Guarded Command Language。多個變數可同時設值(如 l, r := M, N),do 相當於 while 迴圈。條件判斷 if 和一般程式語言不同之處是若不只一個條件成立,程式可任選一個分支執行。註解依照 Algol 系語言的傳統用大括號,但此處我們也把註解視作斷言 (assertion), 表示程式執行到此處一定會成立的條件。這是給人看的資訊,也是我們藉以證明程式正確的重要線索。

證明迴圈正確性的兩大關鍵是其不變量 (loop invariant)界限 (bound)。本程式只有一個迴圈,不變量和界限註記在這一行:

{ Inv: M ≤ l < r ≤ N  ∧  Φ(l,r),   Bound: r - l }

「不變量」事實上並不是一個「量」,而是程式每次執行到迴圈進入點前必定會滿足的條件。此處不變量為 M ≤ l < r ≤ NΦ(l,r)。變數 lr 的初始值分別是 MN. 依照假設,M = l < r = NΦ(l,r) = Φ(M,N) 確實成立。因此第一次執行到迴圈之前,不變量確實是滿足的。

迴圈的進入條件是 l+1 ≠ r,和不變量中的 l < r 合起來看,意思是 lr 不是相鄰的整數。因此m := (l + r) / 2 執行後,m 必定在 lr 之間,但不等於 lr。接下來的 if 敘述中,變數 l 會被設成 m 的先決條件是 Φ(m,r),變數 r 會被設成 m 的先決條件是 Φ(l,m)。不論是哪種情形,執行完 if 敘述後,Φ(l,r) 一定還是成立。所以再回到迴圈開頭時,不變量仍被滿足。

長此以往,直到有一天剛好 l+1 ≠ r 不成立了,也就是說 lr 已是相鄰的整數,和不變量合起來看,剛好我們要的 結束條件 M ≤ l < N ∧ Φ(l,l+1) 就被滿足了!

只是還有兩個但書:首先,if 敘述中的 Φ(m,r)Φ(l,m) 這兩個條件至少要有一個成立。這是 Φ 的另一個要求:

 Φ(l,r)  ∧  l < m < r   ⇒   Φ(l,m)  ∨  Φ(m,r)(*)

其次,我們怎知道迴圈會有停下來的一天呢?這就是「界限」 r-l 處理的部份。由於 M < N, 我們知道 r-l 最初會是一個正整數。而如前所述,每次進入迴圈後,m 的值必定在 lr 之間,但不等於 lr。因此迴圈每執行一次,r-l 就變小一些。當 r-l 等於一時,迴圈就得停了。因此我們知道這迴圈不可能永遠執行下去。

以上便是該程式正確的大略證明。我們只是用中文說說,更仔細的證明是應該要有些數學演算的。關於什麼算是證明、為何要有「形式」證明,希望以後有機會寫寫看。

有哪些函數 Φ 滿足條件 (*) 呢? Van Gasteren 與 Feijen 舉的例子包括:

  • Φ(i,j) = a[i] ≠ a[j],此處 a[M..N] 是某陣列。程式會幫我們找到兩個相鄰但不相等的元素。Van Gasteren 與 Feijen 認為這個特例可能是解說二元搜尋比較合適的例子。
  • Φ(i,j) = a[i] × a[j] ≤ 0, 程式將找到兩個相鄰但正負號不相等,或至少有一個為零的元素。
  • Φ(i,j) = a[i] < a[j],
  • Φ(i,j) = a[i] ∨ a[j], 等等。

再回到最初的問題:怎麼在排序好的陣列中找某個關鍵值呢?理想上我們希望設計某個 Φ,然後套用上面的程式。先賣個關子,下回分解。 :)

參考資料

This entry was posted in 未分類. Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

3 Comments

  1. roy_hu
    Posted 三月 6, 2010 at 5:53 上午 | Permalink

    这是英文blog的中译吗?

    • Posted 三月 6, 2010 at 12:48 下午 | Permalink

      基本上是的。謝謝你兩邊都有看。 :)

      不知為甚麼,寫中文版時我會覺得得多解釋些。因此關於不變量等等便寫了不少。Φ 本來是 relation, 但我覺得這麼寫恐怕嚇到很多人,便改成布林函數了。英文版寫得比較隨便,也可能因為我只是把它當筆記用。

      • roy_hu
        Posted 三月 6, 2010 at 2:09 下午 | Permalink

        你的英文blog比较深,中文的浅显易懂些 :)

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>