二分查找

算法是基础，小蓝同学准备些总结一系列算法分享给大家，这是第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就只能是随机的重复数据中的某一个。

此时，我们会希望知道有多少个目标数存在。或者说我们希望数组的区域。