Posted on 2008-04-02 10:08
dennis 閱讀(2021)
評論(2) 編輯 收藏 所屬分類:
數據結構與算法 、
計算機科學與基礎
編程珠璣Column 4關于binary search的部分相當精彩，
1946年就有人發表binary search，但直到1962第一個正確運行的算法才寫出來。盡管算法描述看起來簡單明了，但是要寫的正確卻是有許多地方要仔細考慮。作者著重強調的是對程序正確性的分析方法，仔細分析方法的pre-condition, invariant,和post-condition。g9老大翻譯過Joshua Bloch在google blog上的文章《
號外，號外，幾乎所有的binary search和mergsort都有錯》，原文在
這里。今天看了下原文，有更新，對于求中值索引的c/c++方法原文仍然是有錯的，本來是這樣：
int mid = ((unsigned) (low + high)) >> 1。
但是在c99標準中，對于兩個signed數值之和，如果溢出結果是未定義的(undefined)，也就是說與編譯器實現相關。上面的代碼應該修改為：
mid = ((unsigned int)low + (unsigned int)high)) >> 1;
我查了下jdk6的java.util.Arrays的源碼，joshua bloch說的這個問題已經解決，現在的binary search如下：
// Like public version, but without range checks.
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
如原文所討論的，采用了>>>操作符替代除以2