Java版数据结构和算法设计二分查找



Java版数据结构和算法设计二分查找。

1、前提：二分查找的前提是需要查找的数组必须是已排序的，我们这里的实现默认为升序

2、原理：将数组分为三部分，依次是中值（所谓的中值就是数组中间位置的那个值）前，中值，中值后；将要查找的值和数组的中值进行比较，若小于中值则在中值前面找，若大于中值则在中值后面找，等于中值时直接返回。然后依次是一个递归过程，将前半部分或者后半部分继续分解为三部分。可能描述得不是很清楚，若是不理解可以去网上找。从描述上就可以看出这个算法适合用递归来实现，可以用递归的都可以用循环来实现。所以我们的实现分为递归和循环两种，可以根据代码来理解算法

3、实现：代码如下

 

[java] view plaincopy

 
  1. package org.cyxl.algorithm.search;  
  2.   
  3. /** 
  4.  * 二分查找 
  5.  * @author cyxl 
  6.  * 
  7.  */  
  8. public class BinarySearch {  
  9.     private int rCount=0;  
  10.     private int lCount=0;  
  11.       
  12.     /** 
  13.      * 获取递归的次数 
  14.      * @return 
  15.      */  
  16.     public int getrCount() {  
  17.         return rCount;  
  18.     }  
  19.   
  20.     /** 
  21.      * 获取循环的次数 
  22.      * @return 
  23.      */  
  24.     public int getlCount() {  
  25.         return lCount;  
  26.     }  
  27.   
  28.     /** 
  29.      * 执行递归二分查找，返回第一次出现该值的位置 
  30.      * @param sortedData    已排序的数组 
  31.      * @param start         开始位置 
  32.      * @param end           结束位置 
  33.      * @param findValue     需要找的值 
  34.      * @return              值在数组中的位置，从0开始。找不到返回-1 
  35.      */  
  36.     public int searchRecursive(int[] sortedData,int start,int end,int findValue)  
  37.     {  
  38.         rCount++;  
  39.         if(start<=end)  
  40.         {  
  41.             //中间位置  
  42.             int middle=(start+end)>>1;    //相当于(start+end)/2  
  43.             //中值  
  44.             int middleValue=sortedData[middle];  
  45.               
  46.             if(findValue==middleValue)  
  47.             {  
  48.                 //等于中值直接返回  
  49.                 return middle;  
  50.             }  
  51.             else if(findValue<middleValue)  
  52.             {  
  53.                 //小于中值时在中值前面找  
  54.                 return searchRecursive(sortedData,start,middle-1,findValue);  
  55.             }  
  56.             else  
  57.             {  
  58.                 //大于中值在中值后面找  
  59.                 return searchRecursive(sortedData,middle+1,end,findValue);  
  60.             }  
  61.         }  
  62.         else  
  63.         {  
  64.             //找不到  
  65.             return -1;  
  66.         }  
  67.     }  
  68.       
  69.     /** 
  70.      * 循环二分查找，返回第一次出现该值的位置 
  71.      * @param sortedData    已排序的数组 
  72.      * @param findValue     需要找的值 
  73.      * @return              值在数组中的位置，从0开始。找不到返回-1 
  74.      */  
  75.     public int searchLoop(int[] sortedData,int findValue)  
  76.     {  
  77.         int start=0;  
  78.         int end=sortedData.length-1;  
  79.           
  80.         while(start<=end)  
  81.         {  
  82.             lCount++;  
  83.             //中间位置  
  84.             int middle=(start+end)>>1;    //相当于(start+end)/2  
  85.             //中值  
  86.             int middleValue=sortedData[middle];  
  87.               
  88.             if(findValue==middleValue)  
  89.             {  
  90.                 //等于中值直接返回  
  91.                 return middle;  
  92.             }  
  93.             else if(findValue<middleValue)  
  94.             {  
  95.                 //小于中值时在中值前面找  
  96.                 end=middle-1;  
  97.             }  
  98.             else  
  99.             {  
  100.                 //大于中值在中值后面找  
  101.                 start=middle+1;  
  102.             }  
  103.         }  
  104.         //找不到  
  105.         return -1;  
  106.     }  
  107. }  

4、测试代码 

 

[java] view plaincopy

 
  1. package org.cyxl.algorithm.search.test;  
  2.   
  3. import org.cyxl.algorithm.search.BinarySearch;  
  4. import org.junit.Test;  
  5.   
  6.   
  7. public class BinarySearchTest {  
  8.     @Test  
  9.     public void testSearch()  
  10.     {  
  11.         BinarySearch bs=new BinarySearch();  
  12.           
  13.         int[] sortedData={1,2,3,4,5,6,6,7,8,8,9,10};  
  14.         int findValue=9;  
  15.         int length=sortedData.length;  
  16.           
  17.         int pos=bs.searchRecursive(sortedData, 0, length-1, findValue);  
  18.         System.out.println(“Recursice:”+findValue+” found in pos ”+pos+”;count:”+bs.getrCount());  
  19.         int pos2=bs.searchLoop(sortedData, findValue);  
  20.           
  21.         System.out.println(“Loop:”+findValue+” found in pos ”+pos+”;count:”+bs.getlCount());  
  22.     }  
  23. }  

5、总结：这种查找方式的使用场合为已排序的数组。可以发现递归和循环的次数是一样的