代码：
// 递归形式1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21/**
* 对半搜索递归算法 T=log(n)
* @param x 要搜索的元素值x
* @param l 在数组l中进行搜索
* @param left 搜索的下标范围最小值
* @param right 搜索的下标范围最大值
* @return
*/
public static int BSearch(int x, int[] l, int left, int right){
if(left<=right){ //若表（子表）非空
int m = (left+right)/2; //对半分割
if(x<l[m]) //搜索左半子表
return BSearch(x, l, left, m-1);
else if(x>l[m]) //搜索右半子表
return BSearch(x, l , m+1, right);
else //搜索成功，返回下标
return m;
}
return -1; //搜索失败
}
// 迭代形式1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19/**
* 对半搜索的迭代算法 T=log(n)
* @param x 要搜索的元素值x
* @param l 在数组l中进行搜索
* @return
*/
public static int BSearch(int x, int[] l){
int m, left=0, right=l.length-1;
while(left<=right){
m=(left+right)/2; //int m = (left+right)/2
if(x<l[m]) //朝左搜索
right = m-1;
else if(x>l[m]) //朝右搜索
left = m+1;
else //x==l[m]，搜索成功
return m;
}
return -1; //搜索失败
}