• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆-19  評論-21  文章-0  trackbacks-0
                 二分查找法(Binary search algorithm)是一個很常見的算法,從<編程珠璣>里再次看到時又有新的收獲。
                 直接看代碼吧,下面是常見的實現(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)化后的代碼為(這個優(yōu)化的思想也挺好的,不知道有沒有一套系統(tǒng)的方法來思考出這個優(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;
            }
             
                 如果直接看這段代碼,有可能不知道是怎么回事。但是運用書中提到的“程序驗證”的方法后,原理就顯而易見了,修改后的代碼為:

             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 

                  “程序驗證” 的思想可以簡述為:不管是驗證一個函數(shù),還是一條語句,一個控制結構(循環(huán),if分支等),都可以采用兩個斷言(前置條件和后置條件)來達到這個目的。前置條件是在執(zhí)行該處代碼之前就應該成立的條件,后置條件的正確性在執(zhí)行完該處代碼后必須得到保證。(ps: 斷言也算是一種驗證的手段)

              上面這段代碼的原理是給定一段區(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行時,始終保證low < high && a[low] < t && a[high] >= t 成立。
              
            2. 在執(zhí)行完6~17行后,肯定滿足條件a[low] < t  && a[high] >=t && high = low + 1,因為循環(huán)退出的條件是 high = low + 1,而該循環(huán)始終保證上面第1條。
              經過這樣的分析后,我們能對程序的正確性有更好的掌握,同時程序也更易理解。

            參考:
              1. 基本上摘自<編程珠璣>,很不錯的一本書,讓我對算法有了新的思考,以前只是看看算法導論如何實現(xiàn)的,沒有思考該算法是如何想出來的,有沒有更簡單的算法(思考的過程類似劉未鵬的<知其所以然(續(xù))>),要堅持這個思考過程需要很多功夫與時間,但效果也很明顯,能對算法有更好的掌握。
            posted on 2011-06-18 15:02 hex108 閱讀(2852) 評論(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,是不是不對?  回復  更多評論
              
            狠狠色丁香久久综合婷婷| 久久精品人人做人人爽电影| 久久人人妻人人爽人人爽| 久久精品18| 国产一区二区精品久久凹凸| 久久最近最新中文字幕大全| 国内精品久久九九国产精品| 久久亚洲美女精品国产精品| 蜜臀久久99精品久久久久久小说| 久久婷婷五月综合国产尤物app| 亚洲精品NV久久久久久久久久| 91精品无码久久久久久五月天| 亚洲国产成人久久精品动漫| 久久99国产精品99久久| 99久久99久久精品国产| 久久午夜无码鲁丝片午夜精品| 久久福利片| 一本色道久久综合亚洲精品| 亚洲综合日韩久久成人AV| 亚洲av成人无码久久精品| 久久久久免费看成人影片| 国产精品久久久福利| 国产99久久九九精品无码| 无夜精品久久久久久| 亚洲精品乱码久久久久久自慰| 麻豆AV一区二区三区久久| 热99re久久国超精品首页| 午夜精品久久久久9999高清| 亚洲AV无一区二区三区久久| 97久久精品无码一区二区天美| 久久er国产精品免费观看8| 亚洲欧洲久久久精品| 国内精品久久人妻互换| 久久国产一片免费观看| 久久久久久亚洲AV无码专区| 精品久久久久中文字幕一区| 四虎影视久久久免费观看| 国产精品久久久久AV福利动漫| 精品久久久久中文字幕一区| 欧美大香线蕉线伊人久久| 精品久久国产一区二区三区香蕉|