CWTEA NET⼆分查时间复杂度计算与分析
⼆分查：
⼆分查⼜称折半查，优点是⽐较次数少，查速度快，平均性能好；其缺点是要求待查表为有序表，且插⼊删除困难。因此，折半查⽅法适⽤于不经常变动⽽查频繁的有序列表。⾸先，假设表中元素是按升序排列，将表中间位置记录的关键字与查关键字⽐较，如果两者相等，则查成功；否则利⽤中间位置记录将表分成前、后两个⼦表，如果中间位置记录的关键字⼤于查关键字，则进⼀步查前⼀⼦表，否则进⼀步查后⼀⼦表。重复以上过程，直到到满⾜条件的记录，使查成功，或直到⼦表不存在为⽌，此时查不成功。 概括之：1）序列有序；2）可以随机访问
争议：表必须有序，表可以顺序⽅式存储，也可以链表⽅式存储。有⼈说，表只能顺序存储；但也有⼈说，折半查也可以⽤跳表实现，跳表即不是顺序存储。 时间复杂度：T（logn）
我们⾸先来看⼀下实现代码：
public static int biSearch(int[]array,int a){sofa评分
int lo =0;
int hi = array.length-1;
int mid;
while(lo <= hi){
mid = lo +(hi - lo)/2;
安徽农业科学
if(array[mid]== a){
return mid;
}else if(array[mid]< a){
lo = mid +1;
}else{
hi = mid -1;
}
}
return-1;
}
分析：
因为⼆分查每次排除掉⼀半的不适合值，所以对于n个元素的情况：
⼀次⼆分剩下：n/2
两次⼆分剩下：n/2/2 = n/4
…
古代建筑名称
m次⼆分剩下：n/(2^m)
在最坏情况下是在排除到只剩下最后⼀个值之后得到结果，即
n/(2^m)=1
所以由上式可得 ： 2^m=n
进⽽可求出时间复杂度为： log2(n)
嘿嘿，粉丝越来越多了，⼤佬，随⼿点个关注呗，不光有新鲜的 LeetCode 题解（多种思路，包教包会，开拓思维），还有经典的⽂章及短视频和⼤家分享，谢谢！⼀起嘿嘿嘿！
绍兴市数字健康服务平台------致所有正在努⼒奋⽃的程序猿们！加油！！有码⾛遍天下 ⽆码⼨步难⾏
1024 - 梦想，永不⽌步!
爱编程 不爱Bug
爱加班 不爱⿊眼圈
固执 但不偏执
气泡式水位计疯狂 但不疯癫
⽣活⾥的菜鸟
⼯作中的⼤神
⾝怀宝藏，⼀⼼憧憬星⾠⼤海
追求极致，⽬标始于⾼⼭之巅
⼀怀揣好奇，梦想改变世界的孩⼦
⼀追⽇逐浪，正在改变世界的极客
你们⽤最美的语⾔，诠释着科技的⼒量
你们⽤极速的创新，引领着时代的变迁
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议