算法系列3：二分查找

二分查找

• 1、二分查找
• • 1.1、暴力解法
  • 1.2、二分查找
  • 1.3、代码实现
• 2、查找第一个和最后一个位置
• • 2.1、找第一个位置
  • 2.2、找最后一个位置
  • 2.3、代码实现
  • 2.4、模板的提炼
• 3、x的平方根
• 4、搜索插入位置
• 5、山峰数组的峰值索引
• 6、寻找峰值
• 7、寻找旋转排序数组中的最小值
• 8、0~n-1中缺失的数字

二分查找是细节非常多的一类算法题，稍有不慎就会编写出死循环代码。

二分查找的适用范围，不仅针对于有序的序列，对于无序但有一定规律的序列，我们也可以使用二分查找算法。

二分查找算法的学习中，我们主要关注以下两点：

• 模板：模板会在前两道题目中总结。
• 算法原理：即这道题的解题思路是什么。

1、二分查找

二分查找

1.1、暴力解法

要在一组序列中找到一个数，暴力解法就是直接遍历序列。但是遍历的时间复杂度为O(logN)，时间效率不太好。所以我们要做优化。

1.2、二分查找

我们可以三个指针：left, right, mid。left指向序列开头，right指向序列结尾，mid求中间位置，计算方式是：

mid = left + (right – left) / 2

这是防溢出的计算形式，因为left + right的值可能超出了整型的最大范围。

假设target大于mid指向值，即target在mid与right之间。由于序列升序，mid及mid之前的数都小于target。我们不妨直接跳过这些较小值，让left走到mid的右边：

假设target小于mid指向值，即target在mid与right之间。由于序列升序，mid及mid之后的数都大于target。我们不妨直接跳过这些较大值，让right走到mid的左边：

当target等于mid指向值，target就找到了。

像这样将序列分成两大段，每次判断都能舍弃一段的问题，具有二段性，可以用二分查找解决。

1.3、代码实现

已知要找的目标值target，设mid指向值为x，

• 当x < target，left来到mid + 1的位置
• 当x > target，right来到mid – 1的位置
• 当x == target，mid就是要返回的下标
• 每次判断结束后，若还未找到target，需更新mid

这里有一个细节：判断肯定是需要循环进行的，那么循环的终止条件是什么？

当left < right的时候，target肯定是没找到的；而当left == right的时候，我们可以这么想，如果我们要找5，而给出序列只有一个5：

[5]

此时left == right的时候，target就找到了。所以循环的终止条件是left > right，即循环的执行条件是left <= right。

class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() – 1, mid = 0;
while (left <= right)
{
mid = left + (right – left)/2;
if (nums[mid] < target) left = mid + 1;
else if (nums[mid] > target) right = mid – 1;
else
return mid;
}

return –1;
}
};

至此，我们就可以提炼出朴素二分查找的模板：

while (left <= right)
{
int mid = left + (right – left)/2;
//int mid = left + (right – left + 1)/2; // 用这个也行没区别

if (...) left = mid + 1;
else if (...) right = mid – 1;
else
...
}

2、查找第一个和最后一个位置

在排序数组中查找元素的第一个和最后一个位置

这道题中，我们不能直接使用朴素二分查找去找target。就算朴素二分查找能够找到target，此时的位置mid不一定是第一个位置或最后一个位置，并且我们也不能够知道当前位置与首尾位置的直接联系。

我们不妨将问题拆分成两部分：找第一个位置、找最后一个位置。

2.1、找第一个位置

我们将序列分为两段：小于target的一段、大于等于target的一段。

如果mid指向值小于target，那么left当然要走到mid的右边。

如果mid指向值大于等于target，right就不能轻易走到mid的左边了，因为如果right走到mid的左边，很可能走到小于target的地方，也就找不到target的第一个位置了。

这时我们让right走到mid的位置。

找第一个位置，还有两个细节：

mid的计算方式

mid有两种计算方式：

mid = left + (right – left) / 2 ···········①

mid = left + (right – left + 1) / 2·······②

当序列元素个数为奇数时，两种计算方式没有区别。

当序列元素个数为偶数时，两种计算方式就有区别：

找第一个位置的过程中，如果left与right已经处于相邻位置：

如果mid计算采用方法①，得出的mid指向当前left所指的值，这个值肯定小于target，于是left向右一格。

如果mid计算采用方法②，得出的mid指向当前right所指的值，这个值肯定大于等于target，那么问题来了：此时mid赋值right，意味着right位置不动，那么下一次判断时计算出mid依旧在right位置上，right依旧不动……这就导致了死循环。

所以找第一个位置，采用方法①计算mid。

循环的终止条件

依旧观察left与right处于邻近位置时的情况。

我们选取好了mid的计算方式后，此时计算mid应该处于left的位置。

left向右一位，left与right刚好重合。由于left此前一直指向小于target的值，所以这一次向右一位与right重合，就一定是target的第一个位置，意味着left == right就是循环终止的条件。

我们还可以进一步思考，如果left与right重合了还进行判断，由于此时计算出来的mid还是重合位置，导致right位置不动，也会引发死循环。

2.2、找最后一个位置

找最后一个位置的思考方法与找第一个位置非常相似，只是我们需要把序列分为：小于等于target的一段、大于target的一段。然后left, right的更新方式有所不同。

找最后一个位置，循环结束的条件也是left == right，而mid的计算得采用上面的方法②。具体原因也可以观察left与right相邻时的情况。

2.3、代码实现

class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.size() == 0) return {–1, –1};

int begin = –1, end = –1;
int left = 0, right = nums.size() – 1, mid = 0;

while (left < right)
{
mid = left + (right – left)/2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
if (nums[left] == target) begin = left;

left = 0, right = nums.size() – 1;
while (left < right)
{
mid = left + (right – left + 1)/2;
if (nums[mid] > target) right = mid – 1;
else left = mid;
}
if (nums[right] == target) end = right;

return {begin, end};
}
};

其实我们还可以做一个小优化，left, right双指针在找完第一个位置的时候，left无需回到0，可以继续配合right找最后一个位置。但为了让代码尽可能分隔开不相互影响，我们还是建议left先回到0。

class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.size() == 0) return {–1, –1}; // 边界情况单独讨论

int begin = 0;
int left = 0, right = nums.size() – 1;

while (left < right)
{
int mid = left + (right – left)/2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
if (nums[left] != target) return {–1, –1}; // 没找到左端点，就不可能找到两个位置
else begin = left;

//right = nums.size() – 1; // left可以不用回去
left = 0, right = nums.size() – 1;
while (left < right)
{
int mid = left + (right – left + 1)/2;
if (nums[mid] > target) right = mid – 1;
else left = mid;
}

return {begin, right};
}
};

第一份代码看起来比较整齐，第二份代码就进行了一些过程和变量创建的优化。

2.4、模板的提炼

// 查找左端点
while (left < right)
{
int mid = left + (right – left)/2;
if (...) left = mid + 1;
else right = mid;
}

// 查找右端点
while (left < right)
{
int mid = left + (right – left + 1)/2;
if (...) right = mid – 1;
else left = mid;
}

对于模板，我们只需记住mid的计算方式；至于if else语句，我们需要就题论题。死记硬背是大忌！

3、x的平方根

x的平方根

题目要求很简单，就是求一个数x开平方，然后舍弃小数部分的整数部分。

这个整数是小于等于x的平方根的，即这个整数的平方小于等于x。

我们可以采取暴力的解法，即用i遍历1 ~ x，刚好i² 小于等于x，i的下一位的平方大于x的时候，我们就返回i。

暴力的解法可以优化。设要返回的值为ret，由于ret² 是小于等于x的，我们就可以将1 ~ x序列分为：平方根小于等于x的一段、平方根大于x的一段。这样问题就具有了二段性，我们就可以用二分查找：

• left, right, mid
• 当ret² 小于等于x，left = mid
• 当ret² 大于x，right = mid – 1

class Solution {
public:
int mySqrt(int x) {
// 考虑到x == 0边界情况
long long left = 0, right = x; // 这里建议也用long long
while (left < right)
{
long long mid = left + (right – left + 1)/2; // 用long long防溢出
if (mid * mid <= x) left = mid;
else right = mid – 1;
}

return left;
}
};

4、搜索插入位置

搜索插入位置

假设要返回的索引为ret。

分析几个样例，我们不难得出，

• 要么ret指向的值，刚好等于target
• 要么ret指向的值，刚好是序列从左往右第一个大于target的值
• 要么ret指向新序列末尾，即原序列末尾的下一位。意味着target比序列中所有值都要大

那么我们就可以把原序列分为两段：小于target的一段、大于等于target的一段。这时我们就可以使用找左端点的二分查找算法。

class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if (target > nums[nums.size()–1]) return nums.size(); // 处理边界条件：target比序列中所有值都要大

int left = 0, right = nums.size() – 1;
while (left < right)
{
int mid = left + (right – left)/2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}

return left;
}
};

5、山峰数组的峰值索引

山峰数组的峰值索引

题目保证了数组都是山脉数组，那么根据给出的示例，山脉数组都是长这样的：

即一升一降。

暴力的解法就是遍历，遇到的数如果比左边大、比右边小，继续向后；当遇到一个数，比左右两边都大，就是峰值，返回索引。

遍历方法显然超时，我们能否进行优化？即找出一个具有二段性的解法？

我们可以将山脉数组，分成递增的一段，和递减的一段：

接着定义下标mid。当arr[mid] > arr[mid – 1]的时候，mid就在递增的一段，由于递增的一段包含峰值，left只能更新到mid，否则可能会跳过峰值。

当arr[mid] < arr[mid – 1]的时候，mid就在递减的一段，right就可以更新到mid的左一位。

当left与right重合，重合位置就是峰值。至此我们找到了二段性，就可以使用二分查找算法解题：

class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left = 0, right = arr.size() – 1;
while (left < right)
{
int mid = left + (right – left + 1)/2;
if (arr[mid] > arr[mid – 1]) left = mid;
else right = mid – 1;
}

return left;
}
};

当然我们也可以这样分序列：

相比前一种解法，峰值跑到了递减的序列里面，所以相关的讨论及操作也需要做一些变化。如何变化这里不再赘述，只给出另一种解法的代码：

class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left = 0, right = arr.size() – 1;
while (left < right)
{
int mid = left + (right – left)/2;
if (arr[mid] < arr[mid + 1]) left = mid + 1;
else right = mid;
}

return right;
}
};

6、寻找峰值

寻找峰值

对于“数组可能包含多个峰值”，我们可以理解为序列可能一直递增：

可能一直递减：

可能只有一个峰值：

可能有多个峰值：

对于“假设 nums[-1] = nums[n] = -∞”，我们就可以想出两个时间复杂度为O(1)的分支操作：如果序列开头呈下降趋势，或者结尾呈上升趋势，我们就可以直接返回开头或者结尾。

但对于一般的序列，暴力的解法就只能是遍历序列，找到峰值就返回，效率显然不行。

我们不妨观察某一个下标i，比较nums[i]与nums[i+1]的关系。

当nums[i] > nums[i+1]的时候，由于序列从nums[i+1]开始向右可能就一直递减，所以我们就不去(i+1)及其右侧找峰值；而题目假设了nums[-1] == -∞，那么从-1到i就一定有一个峰值，我们就去0 ~ i里面找峰值。

当nums[i] < nums[i+1]的时候，由于序列从nums[0]开始向右直到nums[i]可能就一直递增，所以我们就不去i及其左侧找峰值；而题目假设了nums[nums.size()] == -∞，那么从(i+1)到(nums.size() – 1)就一定有一个峰值，我们就去(i+1) ~ (nums.size() – 1)里面找峰值。

此时我们找到了二段性，就可以使用二分查找。将i看作mid，那么我们现在的任务是确定mid的计算方法，即left, right的走法：

• 当nums[mid] > nums[mid+1]的时候，nums[mid]更大，可能为峰值，所以right = mid。如果right = mid – 1，那么right有可能会跳过峰值。
• 当nums[mid] < nums[mid+1]的时候，nums[mid+1]更大，那么nums[mid]就一定不是峰值，所以left = mid + 1。

至此我们就可以编写代码：

class Solution {
public:
int findPeakElement(vector<int>& nums) {
int left = 0, right = nums.size() – 1;

while (left < right)
{
int mid = left + (right – left)/2;
if (nums[mid] > nums[mid + 1]) right = mid;
else left = mid + 1;
}

return right;
}
};

7、寻找旋转排序数组中的最小值

寻找旋转排序数组中的最小值

比如下面的序列：

[ 1, 2, 3, 4, 5, 6 ]

经过一次旋转后，得到：

[ 6, 1, 2, 3, 4, 5 ]

再经过一次旋转后，得到：

[ 5, 6, 1, 2, 3, 4 ]

以此类推…

对于这道题，相信暴力解法大家一看就知道：遍历。我们的任务是怎么做优化。

题目保证了序列所有的值各不相同，那么对于一般的旋转序列，大概都长这样：

高度反映了值的相对大小。我们发现，处于灰线上方的序列，每一个值都是大于总序列最后一个值的，即大于nums[nums.size() – 1]；处于灰线下方的序列，每一个值都是小于等于nums[nums.size() – 1]的。我们就找到了二段性，就可以使用二分查找。

定义一左一右指针left, right，求出mid：

如果nums[mid] > nums[nums.size() – 1]，那么当前mid就处在灰线上方的序列，灰线上方的序列可没有最小值，所以left = mid +1。

如果nums[mid] < nums[nums.size() – 1]，那么当前mid就处在灰线下方的序列，灰线上方的序列可能有最小值，所以right = mid。

当left, right相遇，我们就找到了最小值。

class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() – 1;
while (left < right)
{
int mid = left + (right – left)/2;
if (nums[mid] > nums[nums.size() – 1]) left = mid + 1;
else right = mid;
}

return nums[left];
}
};

当然，以nums[0]为标准讨论二段性，也能解出这道题。只不过在序列有序(升序)的情况下需要单独讨论：

class Solution {
public:
int findMin(vector<int>& nums) {
if (nums[nums.size() – 1] > nums[0]) return nums[0]; // 序列有序，需单独讨论，因为left = mid + 1会跳过最小值

int left = 0, right = nums.size() – 1;
while (left < right)
{
int mid = left + (right – left)/2;
if (nums[mid] >= nums[0]) left = mid + 1;
else right = mid;
}

return nums[left];
}
};

8、0~n-1中缺失的数字

0~n-1中缺失的数字

比如这里有一段序列：

很明显，这就是0~6这么一段公差为1的连续序列中，扣掉了一个3。我们要想办法返回3这个缺失的数字。

当然，这道题有很多种解法。

直接遍历：

class Solution {
public:
int takeAttendance(vector<int>& r) {
int i = 0;
for (; i < r.size(); ++i)
if (i != r[i])
return i;

return i;
}
};

利用hash表：

class Solution {
public:
int takeAttendance(vector<int>& r) {
int sz = r.size();
int hash[10002] = {0};

for (auto& n : r)
{
hash[n]++;
}

int i = 0;
for (; i < sz + 1; ++i)
{
if (hash[i] == 0) return i;
}
return i;
}
};

位运算：

class Solution {
public:
int takeAttendance(vector<int>& r) {
// [0,1,2,3,5]与[1,2,3,4,5]异或
int ret = 0;
for (int i = 0; i < r.size(); ++i)
ret ^= r[i] ^ (i + 1);

return ret;
}
};

高斯求和公式(等差数列求和)：

class Solution {
public:
int takeAttendance(vector<int>& r) {
int sz = r.size();
long sum = (1 + sz) * sz / 2;
for (auto& i : r)
sum -= i;

return sum;
}
};

但是上面方法的时间复杂度都是O(N)。我们来找更优的解法：

我们观察值与索引的关系。0~2序列的值与索引是相等的，而从3下标开始，值总是比索引大。所以我们分析出了序列的二段性。

• records[mid] == mid，命中绿线左边的序列，没有要找索引，left = mid + 1；
• records[mid] != mid，命中绿线左边的序列，可能有要找索引，right = mid。

class Solution {
public:
int takeAttendance(vector<int>& r) {
int left = 0, right = r.size() – 1;
while (left < right)
{
int mid = left + (right – left)/2;
if (r[mid] == mid) left = mid + 1;
else right = mid;
}

return right;
}
};

但是我们直接提交上面代码，会遇到这个问题：

如果一个序列什么都不缺，即循环结束了还是有right == records[right]，那么我们返回的就是序列末位的下一个值：

class Solution {
public:
int takeAttendance(vector<int>& r) {
int left = 0, right = r.size() – 1;
while (left < right)
{
int mid = left + (right – left)/2;
if (r[mid] == mid) left = mid + 1;
else right = mid;
}

return right == r[right] ? right + 1 : right;
}
};