算法经典|二分查找详解

查询算法是非常重要的算法之一，即便不从事算法相关岗位，在CRUD的开发岗中，查询也是常见的业务操作。通常我们是从头到尾查询一个顺序表(数组、链表等)得到我们的结果，这种方式的时间复杂度为O(n)，但针对一些特殊的数据，可以采取更加高效的方式查询。

二分查找

当一个顺序表的数据根据某种方式有序排列的时候，就可以使用二分法查找。二分查找又称折半查找，仅适用于有序的顺序表，其基本思路为：

1.首先将预期结果与顺序表中间位置的元素或对象属性比较，若相等，则查找成功，返回结果；2.若不等，则所查结果只会在中间元素或对象之外的前半部分或者后半部分。3.然后在缩小的范围内继续进行上述两个步骤，知道找到或者确定表中没有对应结果位置。

伪代码如下：

int binarySearch(SeqList L,ElemType key){//在有序表L中查找关键字为key的元素，若存在则返回其所在位置，否则返回-1 int low=0,high=L.length-1; int mid; while(low<=high){ mid=(low+high)/2;//取中间位置 if(L.index[mid]==key){ return mid;//查找成功则返回所在位置 }else if(L.index[mid]>key){ high = mid-1;//从前半部分继续找 }else{ low=mid+1;//从后半部分继续找 } } return -1;}

关于mid的确定

中间值mid的取法可能是学会二分法后，几乎是必遇的一个问题。很多人往往是用上述伪代码中的mid=(low+high)/2来取，这样的写法在low和high的值很大的时候就可能存在溢出的问题，像Java和C等，int、long这些都是有范围的，这样写轻则得不到结果，重则死循环程序崩溃，虽然这种情况在业务操作中极少出现，但还是建议用mid=low+(high-low)/2来取。

复杂度分析

从上述二分查找的思路来说，我们可以将查找的过程用一棵二叉排序树来表示，二分法中也称判定树，根节点即为顺序表的中间元素，根节点的左子树，全是比根节点小的元素，右子树上全是比根节点大的元素，每一棵子树同样满足这一性质，如下图所示。

二叉排序树（判定树）

图中表示的顺序表为{1，2，4，5，7，8，10，11，15，16，17，19}。

从判定树可以看出，查找成功时的查找长度为从根节点到目标节点的路径上的节点数，查找不成功时的查找长度为从根节点到对应失败叶子节点路径上的节点数。

由上述分析可知，二分查找到给定值的比较次数不会超过对应判定树的高度，在等概率查找的情况下，查找成功的平均查找长度为：

二分法平均查找长度

其中h为树的高度，元素个数为n时，树高h=⌈log(n+1)⌉。所以其时间复杂度为O(logn) ，平均情况下比顺序查找效率要高。我们只需要常数的空间保存若干变量，因此空间复杂度：O(1) 。

vlambda博客
学习文章列表