目录
@(二分搜索法)
例如：
int a[]= {1,2,3,4,5,6,7,8};一个数组,我们要从中找到5在其中的位置，最简单就是如下：
for(int i=0;i<a.length;i++){
if(a[i]==5){
return i;
}
}这种方法用大O表达法分析[^1]的话，
i=0；的频度为1
i<a.length的频度为n； ==a.length的长度不是固定的==
if语句也执行了n次
时间复杂度为：
T（n）= 1+ 2*n；
可以写为T（n）=O（n）
使用二分搜索法的话：
~非递归实现~
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[]= {1,2,3,4,5,6,7,8};
System.out.println(binarySearch(a, 7));
System.out.println(binarySearchp(a, 7,0,a.length-1));
}
/**
* 非递归
* @param a 需要查询的数组
* @param x 需要查询的值
* @return 数组中的索引
*/
public static int binarySearch(int a[],int x) {
int l=0,r=a.length-1;
while(l<=r) {
int m=(l+r)/2;
if(a[m]==x) {
return m;
}else if(a[m]>x) {
r=m-1;
}else {
l=m+1;
}
}
return -1;
}~递归实现~
/**
* 递归
* @param a 数组
* @param x 需要查询的值
* @param l 左边的指针
* @param r 右边的指针
* @return 在数组中的索引
*/
public static int binarySearchp(int a[],int x,int l,int r) {
int m=(l+r)/2;
int res=0;
if(a[m]==x) {
return m;
}else if(a[m]>x) {
return binarySearchp(a, x,l,m-1);
}else {
return binarySearchp(a, x,m+1,r);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[]= {1,2,3,4,5,6,7,8};
System.out.println(binarySearch(a, 7));
System.out.println(binarySearchp(a, 7,0,a.length-1));
}==用大O分析二分搜索的算法，可见每次执行一次算法的while循环，搜索数组减少一半，因此最坏情况被执行了O（logn）==
[^1]:大O表示法主要用来
计算算法的时间复杂度
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
