LeetCode刷题总结---二分查找详解

CSDN话题挑战赛第2期
参赛话题：

二分查找简介

二分查找（Binary Search）也叫作折半查找。二分查找有两个要求，一个是数列有序，另一个是数列使用顺序存储结构（比如数组）。

或许你觉得二分查找很简单，确实，二分查找的模板简单而易理解，不过我们不能死记硬背，其中的很多细节需要我们理解和融会贯通。先引入二分查找的经典题目：LeetCode704.二分查找

704.二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

题目中数组为有序数组，同时数组中无重复元素，说明满足了二分查找的前提条件，当看到题目描述满足如上条件的时候，就可以考虑使用二分法了。
具体做法：
在while循环中执行以下步骤

• 首先定义一个数组的中间值middle
• 如果数组中间值与目标值相等直接返回答案
• 如果不相等

1. 如果数组中间值大于目标值，说明数组中间值向右的区间所有数字都大于目标值，右边界right向左靠
2. 如果数组中间值小于目标值，说明数组中间值向左的区间所有数字都小于目标值，左边界left向右靠

二分法两种写法

二分查找一个重要的细节就是边界问题，是 while(left < right) 还是 while(left <= right)，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。而另一个区间则是right = middle和right = middle - 1的问题。

两种区间两种不同的二分写法。

1.区间是「左闭右闭」

• while (left <= right) ，left == right是有意义的，相等时再经历一次循环再结束（left=right+1）
• 中间值大于目标值时右边界要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

代码：

class Solution {
public:
int search(vector<int>& nums, int target) {
    int right = nums.size()-1;
    int left = 0;
    while(left <= right){
        int middle = left + (right - left) / 2;//防止溢出，下面细说
        if(nums[middle] == target){//中间值与目标值相等直接返回答案
            return middle;
        }
        else if(nums[middle] < target){//中间值小于目标值,左边界left向右靠
            left = middle + 1;
        }
        else{
            right = middle - 1;// 中间值大于目标值,右边界right向左靠
        }
    }
    return -1;
}
};

2.区间是「左开右闭」

• while (left < right)，left == right在区间[left, right)是没有意义的，相等时循环就结束
• 中间值大于目标值时右边界要赋值为middle，因为当前的 nums[middle] 是大于 target 的，不能取到 middle，而且区间的定义是 [left, right)，区间本来就取不到right

代码：

class Solution {
public:
int search(vector<int>& nums, int target) {
    int right = nums.size()-1;
    int left = 0;
    while(left < right){
        int middle = left + (right - left) / 2;//防止溢出，下面细说
        if(nums[middle] == target){//中间值与目标值相等直接返回答案
            return middle;
        }
        else if(nums[middle] < target){//中间值小于目标值,左边界left向右靠
            left = middle + 1;
        }
        else{
            right = middle;// 中间值大于目标值,右边界right向左靠
        }
    }
    return -1;
}
};

仔细一看发现二分法也就那样，但是别高兴的太早，二分法重要的思想不在于你把模板背熟了，也不在于上面两种方法的选择。而是需要我们认真分析题目的意思，有些题目看似不满足二分法的条件，但是也能使用二分法（下面会说）我们要清楚地知道在什么样的情况下，搜索的范围是什么，进而确定左右边界。总之需要多练习。

left + (right - left) / 2解决溢出问题

相信很多人跟我一样刚开始不知道这句话到底是什么意思，搜了才知道这是防止int整型数值越界。

因为我们定义左边界（left）和右边界（right）一般都使用 int 类型，那么如果使用mid = (left + right)/2计算中间值可能会导致数据越界。

如果 left 和 right 足够大，mid = (left + right)/2，可能会由于 left+right 导致 int 数据类型越界。所以安全的写法是mid = left + (right - left) / 2或者mid = left + ((right - left) >> 1)，推荐使用右移操作，因为右移比除法快。

二分法相应题目

这里选了几道力扣的题巩固二分法。

35.搜索插入位置 难度：简单

题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的 升序 排列数组
-104 <= target <= 104

解题思路
题目有“排序数值”“找目标值”满足二分查找的条件，而且基本上跟上面的经典题差不多。不过需要注意的是如果目标值不存在于数组中，返回它将会被按顺序插入的位置。返回的是什么？

根据if的判断条件，left左边的值一直保持小于target，right右边的值一直保持大于等于target，而且left最终一定等于right+1，这么一来，循环结束后，在left和right之间画一条竖线，恰好可以把数组分为两部分：left左边的部分和right右边的部分，而且left左边的部分全部小于target，并以right结尾；right右边的部分全部大于等于target，并以left为首。所以最终答案一定在left（right+1）的位置。（思路参考力扣题解）
代码演示

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

34.在排序数组中查找元素的第一个和最后一个位置 难度：中等

题目描述
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

解题思路
题目有“顺序排列的整数数组”，而且规定nlogn时间复杂度，要求找到一个值的左右边界，那么可以使用二分法。

凡是二分法都要考虑到边界的问题，怎么选，边界如何缩小。在这个题目我们需要找到左右边界，可以分别把左右边界算出来。（参考力扣题解）
寻找目标数在数组里的左右边界，有如下三种情况：

• 目标数在数组范围的右边或者左边，返回{-1, -1}
• 目标数在数组范围中，且不存在数组中，返回{-1, -1}
• 目标数在数组范围中，且存在数组中，返回边界

先找其左边界，再找其右边界即可，注意找左边界的时候，由右侧逼近；找右边界的时候，由左侧逼近。
代码演示

class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target){
    int leftBorder = LeftBorder(nums, target);
    int rightBorder = RightBorder(nums, target);
    // 0,0的时候left是-1，使用不能用-1记录不存在
    if (leftBorder == -2 || rightBorder == -2) return {-1, -1};
        if (rightBorder - leftBorder > 1) 
        return {leftBorder + 1, rightBorder - 1};
        return {-1, -1};
}
private:
int LeftBorder(vector<int>& nums, int target){
    int left = 0;
    int right = nums.size() - 1;
    // 记录左边界不存在
    int leftBorder = -2; 
    //找左边界，由右侧逼近
    while (left <= right) {
        int middle = left + ((right - left) / 2);
        if (nums[middle] >= target){ 
            right = middle - 1;
            leftBorder = right;
        } else {
            left = middle + 1;
        }
    }
    return leftBorder;
}
int RightBorder(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    // 记录右边界不存在
    int rightBorder = -2; 
    //找右边界，由右侧逼近
    while (left <= right) {
        int middle = left + ((right - left) / 2);
        if (nums[middle] <= target) {
            left = middle + 1;
            rightBorder = left;
        } else { 
            right = middle - 1;
        }
    }
    return rightBorder;
}
};

69.x的平方根 难度：简单

题目描述
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者x ^ 0.5。

示例 1：

输入：x = 4
输出：2
示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

提示：

0 <= x <= 2^31 - 1

解题思路
本来很简单的题目，但是要求不能使用库函数，那么根据题意可以用二分法。由于 x 平方根的整数部分是满足 k^2 ≤x 的最大 k 值，因此我们可以对 k 进行二分查找，从而得到答案。左边界为0，右边界是x。
代码演示

class Solution {
public:
int mySqrt(int x) {
    int left = 0,right = x,res;
    while(left <= right){
        int middle = left + (right - left) / 2;
        if((long)middle * middle <= x){
            res = middle;
            left = middle + 1;
        }
        else{
            right = middle - 1;
        }
    }
    return res;
}
};

为什么要用long呢？（long long也一样），是为了防止int整型数值溢出，因为题目要求0 <= x <= 2^31 - 1，数值很大。如果用int型平方之后如果用的数很大就会越界，用long long长整型（该数据类型在32位机中表示8个字节，即64位，符号位占一位，-9223372036854775808 ~ 9223372036854775807, 19位长，这是很大的数了），就能解决越界问题。试了一下long也是可以的。

287.寻找重复数 难度：中等

题目描述
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

输入：nums = [1,3,4,2,2]
输出：2

示例 2：

输入：nums = [3,1,3,4,2]
输出：3

提示：

1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

进阶：

如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

解题思路
这道题就没那么简单了，因为比较难想到，而且难的地方是，你可以用多种方法解题，但是题目限定不修改 数组 nums 且只用常量级 O(1) 的额外空间。所以不能使用排序，很多方法都限制了。

而且数组不是有序的，如何想到二分法呢？

可以说这道题就体现了二分法的重要思想，而且题目信息很重要，题目要找的是一个整数，并且这个整数有明确的范围，所以可以使用二分法，二分法必须是有序，那么怎么让变有序呢，我们可以不在数组里面的值二分，而是把值提出来。比如nums = [1,3,4,2,2]，提出1，2，3，4，我们需要查找重复的数，在这查找不就得了？

思路是先猜一个数（搜索范围 [left…right] 里位于中间的数 mid），然后统计数组中<= mid 的元素的个数 count。猜的数范围为1_{n也就是left}right，这里是二分法的体现。每一次猜一个数，然后遍历整个输入数组，进而缩小搜索区间，最后确定重复的是哪个数。

代码演示

class Solution {
public:
int findDuplicate(vector<int>& nums) {
    int left = 1;
    int right = nums.size() - 1;
    while(left <= right){
        int middle = left + (right - left) / 2;
        int cnt = 0;//注意要写在里面，每次都要初始化
        if(left == right) return left;
            for(int i = 0; i < nums.size(); ++i){
            if(nums[i] <= middle){
                cnt++;
            }
                }
        if(cnt > middle){
            right = middle;
        }
        else if(cnt <= middle){
            left = middle + 1;
        }
            }
    return 0; 
}
};

举个例子:
2 3 1 3 4 那么1~n的数为1234 mid=2;

1. cnt=2<=middle，target在[mid+1,right]之间，left=middle+1；
2. left=3,right=4,middle=3;
3. cnt=4>mid，target在[left,mid]之间，right=middle=3;

最后l=r就是答案；
注意点：

• 因为n+1个数中最大的是n，所以right初始化为num.size()-1;
• 因为猜的值是mid，可以把left初始化为1，这样最后返回的middle就是重复的数，不用再考虑下标的事，
• 不过初始化为0也可以最后面+1就行；

总结

二分法还有很多需要注意的地方，继续加油吧，算法任重而道远。