设为首页 - 加入收藏 焦点技术网
热搜:java
当前位置:首页 >

LeetCode总结--二分查找篇

导读:二分查找算法虽然简单,但面试中也比较常见,经常用来在有序的数列查找某个特定的位置。在LeetCode用到此算法的主要题目有:Search Insert PositionSearch for a RangeSqrt(x)Search a 2D MatrixSearch in Rotated Sorted ArraySearch in Rotated Sorted Array II这类题目基本可以分为...。。。
二分查找算法虽然简单,但面试中也比较常见,经常用来在有序的数列查找某个特定的位置。在LeetCode用到此算法的主要题目有:
Search Insert Position
Search for a Range
Sqrt(x)
Search a 2D Matrix
Search in Rotated Sorted Array
Search in Rotated Sorted Array II

这类题目基本可以分为如下四种题型:
1. Search Insert PositionSearch for a Range是考察二分查找的基本用法。基本思路是每次取中间,如果等于目标即返回,否则根据大小关系切去一半,因此时间复杂度是O(logn),空间复杂度O(1)。以Search Insert Position为例,其关键代码写法如下:
    int l = 0;    int r = A.length-1;    while(l<=r)    {        int mid = (l+r)/2;        if(A[mid]==target)            return mid;        if(A[mid]这样当循环停下来时,如果不是正好找到target,l指向的元素恰好大于target,r指向的元素恰好小于target,这里l和r可能越界,不过如果越界就说明大于(小于)target并且是最大(最小)。Search for a Range这道题能更好的解释这一点。其思路是先用二分查找找到其中一个target,然后再往左右找到target的边缘。我们主要看找边缘(往后找)的代码:
    int newL = m;    int newR = A.length-1;    while(newL<=newR)    {        int newM=(newL+newR)/2;        if(A[newM]==target)        {            newL = newM+1;        }        else        {            newR = newM-1;        }                }    res[1]=newR;
我们的目标是在后面找到target的右边界,因为左边界已经等于target,所以判断条件是相等则向右看,大于则向左看,根据上面说的,循环停下来时,l指向的元素应该恰好大于target,r指向的元素应该等于target,所以此时的r正是我们想要的。向前找边缘也同理。

2. Sqrt(x)是数值处理的题目,但同时也可以用二分查找的思想来解决。因为我们知道结果的范围,取定左界和右界,然后每次砍掉不满足条件的一半,直到左界和右界相遇。算法的时间复杂度是O(logx),空间复杂度是O(1)。这里同样是考察二分查找的基本用法。代码如下:
public int sqrt(int x) {    if(x<0) return -1;    if(x==0) return 0;    int l=1;    int r=x/2+1;    while(l<=r)    {        int m = (l+r)/2;        if(m<=x/m && x/(m+1)这里要注意,这里判断相等的条件不是简单的 m == x/m, 而是 m<=x/m && x/(m+1)
public int sqrt(int x) {    if(x<0) return -1;    if(x==0) return 0;    int l=1;    int r=x/2+1;    while(l<=r)    {        int m = (l+r)/2;        if(m==x/m )            return m;        if(x/m
3. Search a 2D Matrix是二分查找算法的多维应用,通过观察不难发现,输入的矩阵行内有序并且行间有序,所以查找只需要先按行查找,定位出在哪一行之后再进行列查找即可,两次二分查找,时间复杂度是O(logm+logn),空间上只需两个辅助变量,因而是O(1),这里不再赘述。

4. Search in Rotated Sorted ArraySearch in Rotated Sorted Array II算是二分查找算法的一个变体。在Search in Rotated Sorted Array中,乍一看感觉数组已经不是有序的了,也就无法用二分查找算法,但仔细分析一下会发现,因为只rotate了一次,如果二分一下,总有一半是有序的,而且和另一半无区间重叠,我们只需要检查有序的一半的前后两个元素就可以确定target可能在哪一半。具体来说,假设数组是A,每次左边缘为l,右边缘为r,还有中间位置是m。在每次迭代中,分三种情况:
(1)如果target==A[m],那么m就是我们要的结果,直接返回;
(2)如果A[m](3)如果A[m]>=A[r],那么说明从l到m一定是有序的,同样只需要判断target是否在这个范围内,相应的移动边缘即可。
根据以上方法,每次我们都可以切掉一半的数据,所以算法的时间复杂度是O(logn),空间复杂度是O(1)。
Search in Rotated Sorted Array II中array有重复元素,按照刚刚的思路,二分之后虽然一半是有序的,但我们会遇到中间和边缘相等的情况,我们就丢失了哪边有序的信息,因为哪边都有可能是有序的结果。假设原数组是{1,2,3,3,3,3,3},那么旋转之后有可能是{3,3,3,3,3,1,2},或者{3,1,2,3,3,3,3},这样的我们判断左边缘和中心的时候都是3,如果我们要寻找1或者2,我们并不知道应该跳向哪一半。解决的办法只能是对边缘移动一步,直到边缘和中间不在相等或者相遇,这就导致了会有不能切去一半的可能。所以最坏情况(比如全部都是一个元素,或者只有一个元素不同于其他元素,而他就在最后一个)就会出现每次移动一步,总共是n步,算法的时间复杂度变成O(n)。

总体来说,二分查找算法理解起来并不算难,但在实际面试的过程中可能会出现各种变体,如何灵活的运用才是制胜的关键。我们要抓住“有序”的特点,一旦发现输入有“有序”的特点,我们就可以考虑是否可以运用二分查找算法来解决该问题。

(编辑: linhuanmars)

网友评论
相关文章