posts - 195, comments - 34, trackbacks - 0, articles - 1

          binary search

          Posted on 2009-09-30 23:47 小強摩羯座 閱讀(87) 評論(0)  編輯  收藏

          在《編程珠璣》中有詳細的討論。主要出于性能方向改進。

          1. 二分法很簡單吧 ,但要想 一次寫對  也不容易吧 ,更何況他的一些擴展應用呢 ,我這里擴展了四種,<P> </P><P>基礎知識 還是牢靠的好</P><P> </P>  
          1. /**  
          2.  * Author: yiminghe  
          3.  * Date: 2008-10-13  
          4.  * Time: 23:50:48  
          5.  * Any problem ,contact yiminghe@fudan.edu.cn.  
          6.  */  
          7. public class BinarySearch {   
          8.   
          9.     //返回中間一個數   
          10.     //12345666689   
          11.     // 6  不確定返回哪個6   
          12.     public static int b1(int[] array, int v) {   
          13.         int left = 0;   
          14.         int right = array.length - 1;   
          15.         while (left <= right) {   
          16.             int middle = (left + right) / 2;   
          17.             if (array[middle] == v) return middle;   
          18.             if (array[middle] > v)   
          19.                 right = middle - 1;   
          20.             else  
          21.                 left = middle + 1;   
          22.         }   
          23.   
          24.         return -1;   
          25.   
          26.     }   
          27.   
          28.     //返回重復元素的最后一個數   
          29.     //123456667   
          30.     //最后一個6位置返回    
          31.     public static int b2(int[] array, int v) {   
          32.         int left = 0;   
          33.         int right = array.length - 1;   
          34.         while (left < right) {   
          35.             int middle = (left + right + 1) / 2;   
          36.             if (array[middle] > v)   
          37.                 right = middle - 1;   
          38.             else  
          39.                 left = middle;   
          40.         }   
          41.   
          42.         if (array[left] == v)   
          43.             return left;   
          44.   
          45.         return -1;   
          46.   
          47.     }   
          48.   
          49.   
          50.     //返回重復元素的最前一個數   
          51.     //123456667   
          52.     //最前一個6位置返回   
          53.     public static int b3(int[] array, int v) {   
          54.         int left = 0;   
          55.         int right = array.length - 1;   
          56.         while (left < right) {   
          57.             int middle = (left + right) / 2;   
          58.             if (array[middle] < v)   
          59.                 left = middle + 1;   
          60.             else  
          61.                 right = middle;   
          62.         }   
          63.   
          64.         if (array[right] == v)   
          65.             return right;   
          66.   
          67.         return -1;   
          68.   
          69.     }   
          70.   
          71.   
          72.     //返回重復元素的最前一個數   
          73.     //1234566689   
          74.     //最前一個6位置返回 ,若找不到,顯示 比他小的離它最大位置,比它小的離它最小位置   
          75.     //如 找 7 ,則 輸出 最后一個6的位置 和 8 的位置   
          76.     public static int b4(int[] array, int v, int flag) {   
          77.         int left = 0;   
          78.         int right = array.length - 1;   
          79.         while (left < right) {   
          80.             int middle = (left + right) / 2;   
          81.             if (array[middle] < v)   
          82.                 left = middle + 1;   
          83.             else  
          84.                 right = middle;   
          85.         }   
          86.   
          87.   
          88.         if (array[right] == v)   
          89.             return right;   
          90.         System.out.println(right - 1 + "  -- " + left);   
          91.         return -1;   
          92.   
          93.     }   
          94.   
          95.   
          96.     public static void main(String[] args) {   
          97.         //                       0, 1, 2, 3  4  5  6  7   
          98.         int[] array = new int[]{12341016161616161618110};   
          99.         //array = new int[]{0, 6};   
          100.         //array = new int[]{6, 7};   
          101.         System.out.println(b1(array, 16));   
          102.         System.out.println(b2(array, 16));   
          103.         System.out.println(b3(array, 16));   
          104.         System.out.println(b4(array, 61));   
          105.   
          106.   
          107.     }   
          108. }  

           





          只有注冊用戶登錄后才能發表評論。


          網站導航:
           
          主站蜘蛛池模板: 临西县| 年辖:市辖区| 乐东| 崇仁县| 宜丰县| 吉首市| 理塘县| 天祝| 若尔盖县| 金坛市| 吉木乃县| 镇宁| 蒲江县| 宜城市| 衡水市| 德令哈市| 丽江市| 安阳县| 聊城市| 库尔勒市| 金寨县| 中西区| 高邮市| 夹江县| 红桥区| 蕲春县| 神木县| 麻阳| 贵溪市| 永福县| 开江县| 贡嘎县| 奇台县| 阜平县| 沈阳市| 房产| 蒲城县| 马山县| 武陟县| 垣曲县| 印江|