二分查找

 1 package search;
 2 
 3 /**
 4  * 二分查找又称折半查找，它是一种效率较高的查找方法。 
 5 　　【二分查找要求】：1.必须采用顺序存储结构 2.必须按关键字大小有序排列。
 6  * @author Administrator
 7  *
 8  */
 9 public class BinarySearch { 
10     public static void main(String[] args) {
11         int[] src = new int[] {1, 3, 5, 7, 8, 9}; 
12         System.out.println(binarySearch(src, 7));
13         System.out.println(binarySearch(src,3,0,src.length-1));
14     }
15 
16     /**
17      * * 二分查找算法 * *
18      * 
19      * @param srcArray
20      *            有序数组 *
21      * @param des
22      *            查找元素 *
23      * @return des的数组下标，没找到返回-1
24      */ 
25    public static int binarySearch(int[] srcArray, int des){ 
26     
27         int low = 0; 
28         int high = srcArray.length-1; 
29         while(low <= high) { 
30             int middle = (low + high)/2; 
31             if(des == srcArray[middle]) { 
32                 return middle; 
33             }else if(des <srcArray[middle]) { 
34                 high = middle - 1; 
35             }else { 
36                 low = middle + 1; 
37             }
38         }
39         return -1;
40    }
41 
42       /**  
43      *二分查找特定整数在整型数组中的位置(递归)  
44      *@paramdataset  
45      *@paramdata  
46      *@parambeginIndex  
47      *@paramendIndex  
48      *@returnindex  
49      */
50     public static int binarySearch(int[] dataset,int data,int beginIndex,int endIndex){  
51        int midIndex = (beginIndex+endIndex)/2;  
52        if(data <dataset[beginIndex]||data>dataset[endIndex]||beginIndex>endIndex){
53            return -1;  
54        }
55        if(data <dataset[midIndex]){  
56            return binarySearch(dataset,data,beginIndex,midIndex-1);  
57        }else if(data>dataset[midIndex]){  
58            return binarySearch(dataset,data,midIndex+1,endIndex);  
59        }else {  
60            return midIndex;  
61        }  
62    } 
63 
64 }