LeetCode总结--⼆分查篇
⼆分查算法虽然简单，但⾯试中也⽐较常见，经常⽤来在有序的数列查某个特定的位置。在LeetCode⽤到此算法的主要题⽬有： 这类题⽬基本可以分为如下四种题型：
1. 和是考察⼆分查的基本⽤法。基本思路是每次取中间，如果等于⽬标即返回，否则根据⼤⼩关系切去⼀半，因此时间复杂度是O(logn)，空间复杂度O(1)。以为例，其关键代码写法如下：
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 = mid+1;
else
r = mid-1;
}
return l;
这样当循环停下来时，如果不是正好到target，l指向的元素恰好⼤于target，r指向的元素恰好⼩于target，这⾥l和r可能越界，不过如果越界就说明⼤于（⼩于）target并且是最⼤（最⼩）。这道题能更好的解释这⼀点。其思路是先⽤⼆分查到其中⼀个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. 是数值处理的题⽬，但同时也可以⽤⼆分查的思想来解决。因为我们知道结果的范围，取定左界和右界，然后每次砍掉不满⾜条件的⼀半，直到左界和右界相遇。算法的时间复杂度是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+1)
return m;
if(x/m<m)
{
r = m-1;
}
else
{
l = m+1;
}
}
return 0;
}
这⾥要注意，这⾥判断相等的条件不是简单的 m == x/m, ⽽是 m<=x/m && x/(m+1)<m+1, 这是因为输出是整型，sqrt(14)=3 但 3 != 14/3. 所以我们需要⼀个范围框住结果。另外根据⼆分查算法的特性，如果不能正好m==x/m停下，那么r指向的数字将正好是结果取整的值。所以我们也可以这样写：
精绝国
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<m)
{
r = m-1;
}
else
{
l = m+1;
无障碍设施}
}
return r;
}
3. 是⼆分查算法的多维应⽤，通过观察不难发现，输⼊的矩阵⾏内有序并且⾏间有序，所以查只需要先按⾏查，定位出在哪⼀⾏之后再进⾏列查即可，两次⼆分查，时间复杂度是O(logm+logn)，空间上只需两个辅助变量，因⽽是O(1)，这⾥不再赘述。黎曼
4. 和算是⼆分查算法的⼀个变体。在中，乍⼀看感觉数组已经不是有序的了，也就⽆法⽤⼆分查算法，但仔细分析⼀下会发现，因为只rotate了⼀次，如果⼆分⼀下，总有⼀半是有序的，⽽且和另
⼀半⽆区间重叠，我们只需要检查有序的⼀半的前后两个元素就可以确定target可能在哪⼀半。具体来说，假设数组是A，每次左边缘为l，右边缘为r，还有中间位置是m。在每次迭代中，分三种情况：
（1）如果target==A[m]，那么m就是我们要的结果，直接返回；
（2）如果A[m]<A[r]，那么说明从m到r⼀定是有序的（没有受到rotate的影响），那么我们只需要判断target是不是在m到r之间，如果是则把左边缘移到m+1，否则就target 在另⼀半，即把右边缘移到m-1。
（3）如果A[m]>=A[r]，那么说明从l到m⼀定是有序的，同样只需要判断target是否在这个范围内，相应的移动边缘即可。
根据以上⽅法，每次我们都可以切掉⼀半的数据，所以算法的时间复杂度是O(logn)，空间复杂度是O(1)。
中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)。
总体来说，⼆分查算法理解起来并不算难，但在实际⾯试的过程中可能会出现各种变体，如何灵活的运⽤才是制胜的关键。我们要抓住“有序”的特点，⼀旦发现输⼊有“有序”的特点，我们就可以考虑是否可以运⽤⼆分查算法来解决该问题。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议