二分查找法的实现和应用汇总

《二分查找法的实现和应用汇总》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、二分查找法的实现和应用汇总在学习算法的过程中，我们除了要了解某个算法的基本原理、实现方式，更重要的一个环节是利用big-O理论来分析算法的复杂度。在时间复杂度和空间复杂度之间，我们又会更注重时间复杂度。时间复杂度按优劣排差不多集中在：O(1),O(logn),O(n),O(nlogn),O(n2),O(nk),O(2n)到目前位置，似乎我学到的算法中，时间复杂度是O(logn),好像就数二分查找法，其他的诸如排序算法都是O(nlogn)或者O(n2)。但是也正是因为有二分的O(logn),才让很多O(n2)缩减到只要O(nlogn)

2、。 关于二分查找法二分查找法主要是解决在“一堆数中找出指定的数”这类问题。而想要应用二分查找法，这“一堆数”必须有一下特征：·存储在数组中·有序排列所以如果是用链表存储的，就无法在其上应用二分查找法了。（曽在面试被问二分查找法可以什么数据结构上使用：数组？链表？）至于是顺序递增排列还是递减排列，数组中是否存在相同的元素都不要紧。不过一般情况，我们还是希望并假设数组是递增排列，数组中的元素互不相同。 二分查找法的基本实现二分查找法在算法家族大类中属于“分治法”，分治法基本都可以用递归来实现的，二分查找法的递归实现如下：intbsear

3、ch(intarray[],intlow,inthigh,inttarget){if(low>high)return-1;intmid=(low+high)/2;if(array[mid]>target)returnbinarysearch(array,low,mid-1,target);if(array[mid]

4、递归，所以二分查找法也可以不用递归实现，而且它的非递归实现甚至可以不用栈，因为二分的递归其实是尾递归，它不关心递归前的所有信息。intbsearchWithoutRecursion(intarray[],intlow,inthigh,inttarget){while(low<=high){intmid=(low+high)/2;if(array[mid]>target)high=mid-1;elseif(array[mid]

5、raydoesnotcontainthetargetreturn-1;}复制代码 只用小于比较（<）实现二分查找法在前面的二分查找实现中，我们既用到了小于比较（<）也用到了大于比较（>），也可能还需要相等比较（==）。而实际上我们只需要一个小于比较（<）就可以。因为错逻辑上讲a>b和b

6、

7、(b

8、符的逻辑值。不过在整型数据面前，这些关系运算符之间的逻辑关系还是成立的，而且在开发过程中，我们还是会遵循这些逻辑等价关系来重载关系运算符。干嘛要搞得那么羞涩，只用一个关系运算符呢？因为这样可以为二分查找法写一个template，又能减少对目标对象的要求。模板会是这样的： templateinlineintBSearch(T&array,intlow,inthigh,V&target){while(!(high

9、[mid])high=mid-1;elseif(array[mid]

10、法找寻边界值，也就是说在有序数组中找到“正好大于（小于）目标数”的那个数。用数学的表述方式就是：    在集合中找到一个大于（小于）目标数t的数x，使得集合中的任意数要么大于（小于）等于x，要么小于（大于）等于t。 举例来说：给予数组