二分查找法（
Binary search algorithm）是一個(gè)很常見(jiàn)的算法，從＜編程珠璣＞里再次看到時(shí)又有新的收獲。
直接看代碼吧，下面是常見(jiàn)的實(shí)現(xiàn)代碼：
int binary_search(int *a, int num, int t)
{
int start = 0, end = num - 1;
while(end >= start){
int middle = (start + end) / 2;
int tmp = a[middle];
if(tmp < t){
start = middle + 1;
}else if(tmp > t){
end = middle - 1;
}else{
return middle;
}
}
return -1;
}
優(yōu)化后的代碼為（這個(gè)優(yōu)化的思想也挺好的，不知道有沒(méi)有一套系統(tǒng)的方法來(lái)思考出這個(gè)優(yōu)化思路）：
int binary_search(int *a, int num, int t)
{
int low = -1, high = num - 1;
while(low + 1 != high){
int middle = (low + high) / 2;
if(a[middle] < t){
low = middle;
}else{
high = middle;
}
}
if(a[high] != t)
return -1;
else
return high;
}
如果直接看這段代碼，有可能不知道是怎么回事。但是運(yùn)用書(shū)中提到的“
程序驗(yàn)證”的方法后，原理就顯而易見(jiàn)了，修改后的代碼為：
1 int binary_search(int *a, int num, int t)
2 {
3 int low = -1, high = num - 1;
4
5 //invariant: low < high && a[low] < t && a[high] >= t
6 while(low + 1 != high){
7 int middle = (low + high) / 2; ＝＝＞ int middle = low + (high - low) / 2; //防止溢出
8 if(a[middle] < t){
9 low = middle;
10 }else{
11 high = middle;
12 }
13 } 14 //assert： low +1 = high && a[low] < t && a[high] >= t
15
16 if(a[high] != t)
17 return -1;
18 else
19 return high;
20 }
21 “程序驗(yàn)證” 的思想可以簡(jiǎn)述為：不管是驗(yàn)證一個(gè)函數(shù)，還是一條語(yǔ)句，一個(gè)控制結(jié)構(gòu)（循環(huán)，if分支等），都可以采用兩個(gè)斷言（前置條件和后置條件）來(lái)達(dá)到這個(gè)目的。前置條件是在執(zhí)行該處代碼之前就應(yīng)該成立的條件，后置條件的正確性在執(zhí)行完該處代碼后必須得到保證。（ps: 斷言也算是一種驗(yàn)證的手段）
上面這段代碼的原理是給定一段區(qū)間 (low, high] ，如果満足 a[low] < t && a[high] >=t && high = low + 1，那么有兩種情況存在：1. a[high] = t ; 2.與t相等的元素不存在。由于數(shù)組a 肯定滿足條件a[low] < t && a[high] >=t，所以該算法要做的就是把區(qū)間 (-1, num -1] 縮小到(low, low+1]。
1. 在執(zhí)行代碼6~17行時(shí)，
始終保證low < high && a[low] < t && a[high] >= t 成立。
2. 在執(zhí)行完6~17行后，肯定滿足條件a[low] < t && a[high] >=t && high = low + 1，因?yàn)檠h(huán)退出的條件是 high = low + 1，而該循環(huán)始終保證
上面第１條。
經(jīng)過(guò)這樣的分析后，我們能對(duì)程序的正確性有更好的掌握，同時(shí)程序也更易理解。
參考：
１. 基本上摘自＜
編程珠璣＞，很不錯(cuò)的一本書(shū)，讓我對(duì)算法有了新的思考，以前只是看看算法導(dǎo)論如何實(shí)現(xiàn)的，沒(méi)有思考該算法是如何想出來(lái)的，有沒(méi)有更簡(jiǎn)單的算法（思考的過(guò)程類似劉未鵬的＜
知其所以然（續(xù)）＞），要堅(jiān)持這個(gè)思考過(guò)程需要很多功夫與時(shí)間，但效果也很明顯，能對(duì)算法有更好的掌握。
posted on 2011-06-18 15:02
hex108 閱讀(2881)
評(píng)論(3) 編輯 收藏 引用 所屬分類:
Algorithm