二分查找

微信公众号：Vegout 如有问题或建议，请公众号留言

二分查找

数据是海量的，从中提取有价值的信息是必要的，提取的过程也就是查找的过程。简单粗暴就是顺序查找，任何东西我一个一个来，不管你是有序无序，对我来说都一样。跟今天咱们所说的二分查找相比，顺序查找是低效的，二分查找可以更快的查找出结果。但同时，二分查找也是有开销的，如果说我们在一个数组中查找一个元素，那么二分查找要求这个数组是有序的。构建这个有序的数组就是相对于顺序查找多出来的开销。

假设我们有这么一个有序数组{0,1,2,3,4,5,6,7,8,9,10,16,35,67,77,778}，如果想要查找16所在位置，二分查找的思想就是先将这个数组一分为二，找到中间元素，进行比较，如果大于中间元素，就去右子数组中继续这个过程，如果小于这个元素就去左子数组中继续这个过程，如果相等，那么就返回这个位置。这个数组有16个元素，下标是0到15，中间元素下标就是7，下标是7的元素也就是7，16大于7，于是我们再去下标8到15（右子数组）中重复查找过程，找到新的中间元素是坐标11，对应元素正好是16，于是返回11。

这个过程可以简单的用递归来实现，代码如下

    public static int search(int[] array,int key,int lo,int hi){
        if (lo>hi)return -1;
        int mid  = lo + (hi-lo)/2;
        if (key<array[mid])return search(array,key,lo,mid-1);
        else if(key>array[mid])return search(array,key,mid+1,hi);
        else return mid;
    }

也可以采取非递归的方式

public static int search(int[] array,int key,boolean notrecursion){
    int lo =0;
    int hi = array.length-1;
    while (lo<=hi){
        int mid  = lo +(hi-lo)/2;
        if (key<array[mid]) hi=mid-1;
        else if (key>array[mid])lo=mid+1;
        else return mid;
    }
    return -1;
}

这个代码实现的就是二分查找，其实我们对这个代码改动一点点就可以实现查找小于当前元素的元素个数这一功能。以上代码采取返回-1的方式告知用户未查找到此元素，我们把-1改为lo,这样就实现了查找小于当前元素的元素个数的功能。为什么呢？

对与递归这个示例代码来说，什么时候会进入if(lo>hi)这个分支？只有上次循环中lo等于了hi等于了mid,并且key不等与array[mid]，于是亦或mid-1赋值给了hi,亦或mid+1赋值给了lo,反正使得lo大于了hi，此刻返回lo,lo大于hi,说明array[lo]定是大于我们所查找的Key,并且lo等于mid+1,于是lo也就是小于key的元素的数量值。lo正好等于小于所查找元素的个数。

代码中还有一个需要注意的地方，计算中间元素坐标用的是lo+(hi-lo)/2而不是(hi+lo)/2这是为什么呢？得出的结果是一样的，只不过前者避免了溢出的发生，我们使用的Int数据类型，他表示的数是有范围的，如果超出了这个范围发生了溢出，我们计算出的mid就可能不处在lo和hi之间，二分查找就会失效。

与顺序查找相比，二分查找确实是可以更快的查找出结果，但也正如前文所说，在构建这个有序数组上存在着一定的开销，也就是我们的插入动作有些缓慢，为了在保持高效二分查找的同时，也保证插入的高效性，也就需要一个新的数据结构，这个我们下文再谈。