分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归的解这些子问题，然后将各个子问题的解合并得到原问题的解。下面有两种描述算法的代码，其中一种是用递归来实现的。
二分搜索方法充分利用了元素间的次序关系，采用分治策略，可在最坏情况下用O(logn)时间完成搜索任务。
1.根据问题思路的描述直接写得的代码：
public class BinarySearch{ public static int binarySearch(int a[],int x,int n) { int left=0; int right=n-1; while(left<=right) { int middle=(left+right)/2; if(x==a[middle]) return middle; if(x>a[middle]) left=middle+1; else right=middle-1; } return -1; } public static void main(String[] args) { int a[]={1,12,23,34,55,76,87,98,99,101,120}; int b=binarySearch(a,1,5); int c=binarySearch(a,98,a.length); int d=binarySearch(a,100,a.length); System.out.println(b); System.out.println(c); System.out.println(d); }}
2.根据递归思想写得的代码
public class BinarySearch2{ public static int binarySearch(int a[],int x,int m,int n) { int left=m; int right=n-1; while(left<=right) { int middle=(left+right)/2; if(x==a[middle]) return middle; if(x>a[middle]) return binarySearch(a,x,middle+1,right); else return binarySearch(a,x,left,middle-1); } return -1; } public static void main(String[] args) { int a[]={1,12,23,34,55,76,87,98,99,101,120}; int b=binarySearch(a,1,0,5); int c=binarySearch(a,98,0,a.length); int d=binarySearch(a,100,0,a.length); System.out.println(b); System.out.println(c); System.out.println(d); }}
相比之下，1算法的空间复杂度要低一些，也更加简练。
