二分查找

1 int[] arr = { 1,2,3,4,5,6,7,8,9};    
2 //Arrays.sort(arr);//二分查找，数组要有序的哇
3 System.out.println(Arrays.binarySearch(arr, 5));

运行结果：4

binarySearch
public static int binarySearch(int[] a,
                               int key)使用二分搜索法来搜索指定的 int 型数组，以获得指定的值。必须在进行此调用之前对数组进行排序（通过 sort(int[]) 方法）。如果没有对数组进行排序，则结果是不确定的。如果数组包含多个带有指定值的元素，则无法保证找到的是哪一个。 

参数：
a - 要搜索的数组
key - 要搜索的值 
返回：
如果它包含在数组中，则返回搜索键的索引；否则返回 (-(插入点) - 1)。插入点 被定义为将键插入数组的那一点：即第一个大于此键的元素索引，如果数组中的所有元素都小于指定的键，则为 a.length。注意，这保证了当且仅当此键被找到时，返回的值将 >= 0。

so easy! 呃，真好意思啊，自己写个二分查找吧

 1     int binSearch0(int arr[],int start,int end,int key){
 2         if(arr==null||arr.length==0||start>end)
 3             return -1;
 4         int i=(start+end)/2;
 5         if(arr[i]==key)
 6             return i;
 7         else if(arr[i]<key)
 8             return binSearch0(arr,i+1,end,key);
 9         else
10             return binSearch0(arr, start, i-1, key);
11             
12     }
13     int binSearch(int arr[],int key){    //找到，则返回下标，找不到就返回-1
14         return binSearch0(arr,0,arr.length-1,key); 
15     }

那个非递归的呢

 1     int binSearch(int arr[],int key){
 2         if(arr==null||arr.length==0)
 3             return -1;
 4         int i=0,j=arr.length-1,m;
 5         while(i<=j){
 6             m=(i+j)/2;
 7             if(arr[m]==key){
 8                 return m;
 9             }else if(arr[m]<key){
10                 i=m+1;
11             }else{
12                 j=m-1;
13             }
14         }
15         return -1;    
16     }