1.二分查找算法思想:
将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x
2.时间复杂度:
匹配k次后,剩下的元素个数为: n/(2^k)
根据 n/(2^k) >=1 , 即可求出时间复杂度 O(log2 n) ,以2为底, n的对数.
3.算法要求:
(1)待查询的序列必须按关键字大小排列;
(2)待查询的序列必须采用顺序存储结构;
4.优缺点:
优点:比较次数少,查找速度快;
缺点:必须采用顺序存储结构,插入删除困难;
5.算法的递归实现:
6.算法的非递归实现:
public class Main1 {
public static int binarySearch(int []a,int num){
int len=a.length;
int high=len-1;
int low=0;
while(low<=high){
int mid=(high+low)>>1;
if(a[mid]==num)
return mid;
else if(a[mid]<num)
low=mid+1;
else
high=mid-1;
}
return -1;
}
public static void main(String args[]){
int []a={
1,10,30,34,40,45,59};
int index=Main1.binarySearch(a, 30);
System.out.println(index);
}
}
7.算法的递归实现:
public class Main1 {
public static int binarySearch_(int []a,int low, int high,int num){
if(low<=high){
int mid=(low+high)>>1;
if(a[mid]==num)
return mid;
else if(a[mid]<num)
low=mid+1;
else
high=mid-1;
return binarySearch_(a,low,high,num);
}else
return -1;
}
public static void main(String args[]){
int []a={
1,10,30,34,40,45,59};
int index=Main1.binarySearch_(a, 0,a.length-1,3);
System.out.println(index);
}
}
今天的文章二分查找算法(Java)分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/9875.html