浅谈二分法查找和原始算法查找的效率对比
我就废话不多说了，大家还是直接看代码吧！
importjava.text.MessageFormat;
publicclassAppTest{
staticintlength=70000000;
staticint[]array=newint[length];
static{
for(inti=0;iend||
targetarr[arr.length-1]){
return-1;
}elseif(targetarr[middle]){
returnfindIndex(arr,middle+1,end,target);
}
return-1;
}
publicstaticintfindIndexByFor(int[]arr,inttarget){
intindex=0;
for(inti:arr){
if(i==target){
returnindex;
}
index++;
}
return-1;
}
}
查找结果：
总结：
总结过我们可以看出，二分法查找几乎是不耗时，所以方法是很重要的
补充知识：顺序查找与二分查找时间复杂度的比较
注意要点：通过System.currentTimeMills();来获取当前时间，来计算该算法运行运算时间顺序查找的时间复杂度为O(n)
二分查找的时间复杂度为O(log(n))
但两者的运行时间的结果却千差万别，可知当计算量很大的情况下算法优化的必要性。
importjava.util.Arrays;
publicclassMain{
publicstaticinta[]=newint[10000*10000];
publicstaticvoidmain(String[]args){
for(inti=0;i<10000*10000;i++){
a[i]=i+1;
}
inttarget=10000*10000;
//计算顺序查找所用时间
longstart=System.currentTimeMillis();
find(target);
longend=System.currentTimeMillis();
System.out.println(end-start+"ms");
//计算二分查找所用时间
start=System.currentTimeMillis();
Arrays.binarySearch(a,target);
end=System.currentTimeMillis();
System.out.println(end-start+"ms");
}
privatestaticvoidfind(inttarget){
for(inti=0;i<10000*10000;i++){
if(a[i]==target){
return;
}
}
}
}
运行结果：
55ms
0ms
以上这篇浅谈二分法查找和原始算法查找的效率对比就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。