# 二分查找 ## 现实中的例子： > 我们日常生活中，很多人应该有这种经历，朋友、同学或者同事淘了个宝贝，神秘兮兮的过来让大家猜多少钱，在约定一个价格范围之后（比如10-100），大家会七嘴八舌的猜起价格来： > > 「50」 「高了」 > > 「30」 「低了」 > > 「40」 「高了」 > > 「36」 「对了」 > > 如果我们用顺序遍历的逻辑，最差需要91次，才能猜到价格，现实生活中，没人会这么干，我们采用上面这种逻辑，只需要4次就猜到价格了，快了几十倍，而且数据量越大，优势越明显。 ## 定义： > 针对的是`一个有序的数据集合`（这点很重要），查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。注意到二分查找针对的必须是已经排序过的有序数组，否则不能使用该算法。  ## 代码： ~~~ /** * 二分查找 * @param $nums * @return mixed */ function binary_search($nums,$num){//传入数组和需要查找的数据 return binary_search_internal($nums,$num,0,count($nums)-1); } function binary_search_internal($nums,$num,$low,$high){ if($low>$high){ return -1;//没有找到，即数组中不存在这个值 } $mid = floor(($low+$high)/2); if($num>$nums[$mid]){ return binary_search_internal($nums,$num,$mid+1,$high); }elseif($num<$nums[$mid]){ return binary_search_internal($nums,$num,$low,$mid-1); }else{ return $mid; } } $nums = [1,2,3,4,5,6]; $index = binary_search($nums,5); print $index; ~~~ ## 总结： 1. 时间复杂度：O(logn) 2. 二分查找在线性表结构中的应用非常广泛 3. 针对有序数组 4. 二分查找适用于变动不是很频繁的静态序列集，如果序列集变动很频繁，经常进行插入删除操作，那么就要不断维护这个序列集的排序，这个成本也很高，因此，这种情况下就不适用二分查找了，比如我们的数据库查询，增删改查很频繁，显然不是通过二分查找来进行查询的，后面我们会讨论，如何针对动态变化的序列集进行查询操作。