二分搜索法

　　给定已排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。

　　二分搜索法的基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与x进行比较。如果x=a[n/2]，则找到x，算法终止。如果x<a[n/2]，则只要在数组a的左半部分继续搜索x。如果x>a[n/2]，则只要在数组右半部分继续搜索x。

 1 public class binarySearch {
 2     
 3     public static int binSearch(int a[],int n,int x){
 4         //在数组a[]中搜索x，找到x返回位置，没找到返回-1
 5         int left = 0,right = n-1;
 6         while(left<=right){
 7             int middle = (left+right)/2;
 8             if(a[middle]==x) 
 9                 return middle;
10             else if(a[middle]>x) 
11                 right=middle-1; //肯定不是middle，所以-1
12             else
13                 left=middle+1;
14         }
15         return -1;
16     }
17     
18     public static void main(String[] args) {
19         int a[]={1,3,5,7,9,23,41,64};
20         System.out.println(binSearch(a, a.length, 64));
21     }
22 
23 }