LeetCode总结--二分查找篇

二分查找算法尽管简单，但面试中也比較常见。经经常使用来在有序的数列查找某个特定的位置。在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 Position和Search
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 = mid+1;
else
r = mid-1;
}
return l;

这样当循环停下来时，假设不是正好找到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;

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;
}