随笔-19  评论-21  文章-0  trackbacks-0
     二分查找法(Binary search algorithm)是一个很常见的算法,从<编程珠玑>里再次看到时又有新的收获。
     直接看代码吧,下面是常见的实现代码:
    
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;
}   

      优化后的代码为(这个优化的思想也挺好的,不知道有没有一套系统的方法来思考出这个优化思路):
     
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;
}
 
     如果直接看这段代码,有可能不知道是怎么回事。但是运用书中提到的“程序验证”的方法后,原理就显而易见了,修改后的代码为:

 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 

      “程序验证” 的思想可以简述为:不管是验证一个函数,还是一条语句,一个控制结构(循环,if分支等),都可以采用两个断言(前置条件和后置条件)来达到这个目的。前置条件是在执行该处代码之前就应该成立的条件,后置条件的正确性在执行完该处代码后必须得到保证。(ps: 断言也算是一种验证的手段)

  上面这段代码的原理是给定一段区间 (low, high] ,如果満足 a[low] < t  && a[high] >=t && high = low + 1,那么有两种情况存在:1. a[high] = t ; 2.与t相等的元素不存在。由于数组a 肯定满足条件a[low] < t  && a[high] >=t,所以该算法要做的就是把区间 (-1, num -1] 缩小到(low, low+1]。  
      1. 在执行代码6~17行时,始终保证low < high && a[low] < t && a[high] >= t 成立。
  
2. 在执行完6~17行后,肯定滿足条件a[low] < t  && a[high] >=t && high = low + 1,因为循环退出的条件是 high = low + 1,而该循环始终保证上面第1条。
  经过这样的分析后,我们能对程序的正确性有更好的掌握,同时程序也更易理解。

参考:
  1. 基本上摘自<编程珠玑>,很不错的一本书,让我对算法有了新的思考,以前只是看看算法导论如何实现的,没有思考该算法是如何想出来的,有没有更简单的算法(思考的过程类似刘未鹏的<知其所以然(续)>),要坚持这个思考过程需要很多功夫与时间,但效果也很明显,能对算法有更好的掌握。
posted on 2011-06-18 15:02 hex108 阅读(2532) 评论(3)  编辑 收藏 引用 所属分类: Algorithm

评论:
# re: 二分查找 -- 来自编程珠玑 2011-06-24 10:11 | tank
你的程序有错,你知道不??  回复  更多评论
  
# re: 二分查找 -- 来自编程珠玑 2011-06-24 15:53 | hex108
@tank
请指教,谢谢~  回复  更多评论
  
# re: 二分查找 -- 来自编程珠玑[未登录] 2012-01-18 04:02 | terry
1 2 2 3 查找2,是不是不对?  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理