算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第5篇《二分查找》,非常赞!希望对大家有帮助,大家会喜欢!
前面系列文章:
二分查找,就和他的名字一样,把一个数组找到他的中间的值和我想要找的值,进行对比,这个时候可以分为三种情况 1、比中间值大,我就到中间值到最大值的范围内去找。
2、比中间值小,那就去最小值和中间值之间去寻找。 如果正好相等那恭喜你找到了。然后照这个思路不断的递归迭代就可以确定是否有对应的值了。
publicint rank(Key key ){
intl1= keys.length;
intl0=0;
while(l0<l1){
intmid=l0+(l1+l0)/2;
intb = key.compareTo(keys[mid]);
if(b<0) l0=mid+1; //+1和下面-1 的作用是为了找不到是跳出
elseif(b>0) l1=mid-1;
elsereturnmid;
}
returnl0;
}
特性: 查找速度 lgN 插入速度在N-2N之间
优缺点:
相对于普通顺序查找速度由二次方到对数级块了很多。
缺陷:数组必须有序的
应用:
用二分查找法找寻边界值
之前的都是在数组中找到一个数要与目标相等,如果不存在则返回-1。我们也可以用二分查找法找寻边界值,也就是说在有序数组中找到“正好大于(小于)目标数”的那个数。
用数学的表述方式就是:
在集合中找到一个大于(小于)目标数t的数x,使得集合中的任意数要么大于(小于)等于x,要么小于(大于)等于t。
用二分查找法找寻区域
之前我们使用二分查找法时,都是基于数组中的元素各不相同。假如存在重复数据,而数组依然有序,那么我们还是可以用二分查找法判别目标数是否存在。不过,返回的index就只能是随机的重复数据中的某一个。
此时,我们会希望知道有多少个目标数存在。或者说我们希望数组的区域。