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

binary search

Posted on 2009-09-30 23:47 小强摩羯座 阅读(83) 评论(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[]{1, 2, 3, 4, 10, 16, 16, 16, 16, 16, 16, 18, 110};   
  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, 6, 1));   
  105.   
  106.   
  107.     }   
  108. }  

 





只有注册用户登录后才能发表评论。
网站导航: