LeetCode总结之二分查找篇

LeetCode总结之二分查找篇2015-10-02二分查找算法虽然简单，但面试中也比较常见，经常用来在有序的数列查找某个特定的位置。在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;elser = 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;

我们的目标是在后面找到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+1）return m;if（x/m<m）{r = m-1;}else{l = m+1;}}return 0;}