2007年4月2日

你會寫 Binary Search 嗎?

zmx 在他版上說到:他最近面試了 {資工、資科、資管、應數} 共 5 人,沒有一個人能夠一次寫對 binray search。

這讓我覺得很訝異,自己動手寫了一個,發現我也沒有辦法一次正確,還是習慣性地錯在迴圈條件 (小於 vs. 不大於) 以及邊界更新 (差一) 上面。

不過我犯的錯誤只要有簡單的測試程式就可以解決,應該不會是學長提到的 "20 年才找到的 Bug"。為了弄清楚,我用 Google 找到以下的資料:
  1. 原來 zmx 早就在他的 blog 提過,當初也看過,卻還是忘記了......
  2. Joshua Bloch 在 Google Research 上的文章,說明了這個很容易被忽略的問題
  3. 上面那篇文章的中文翻譯