算法：二分查找题目练习

题目一：二分查找

朴素的二分模版

题目二：在排序数组中查找元素的第⼀个和最后⼀个位置

查找区间左端点

查找区间右端点

查找区间左端点二分模版

查找区间右端点二分模版

题目三：搜索插⼊位置

题目四：x的平方根

题目五：山峰数组的峰顶

题目六：寻找峰值

题目七：搜索旋转排序数组中的最小值

题目八：0〜n-1中缺失的数字

二分查找算法原理

二分查找算法适用于数组有序的情况，当然数组如果无序但是能够找到一个规律，也是可以使用二分查找算法的

二分查找算法模版

这里的模块需要理解之后再记忆

有三个模版，分别是：

①朴素的二分模版
②查找左边界的二分模版
③查找右边界的二分模版

题目一：二分查找

给定一个 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

解法一：暴力解法

初看这个题，可以很容易想到暴力解法，也就是遍历一遍这个数组，直到找到这个目标值target，返回该目标值的下标即可，若没有找到该目标值，就返回-1即可

暴力解法时间复杂度是O(N)

解法二：二分查找算法

二分查找算法是当数组有二段性的时候，就能够使用二分查找算法了，因为在暴力解法中，依次遍历一次只能排除一个数，而如果数组有二段性，二分查找算法就可以依次排除一块区域的数，因此效率比较高

二段性就是我们所发现一个规律，根据这个规律选取一个点之后(一般选取中间的点)，能够将数字分成两部分，根据规律能舍去其中一部分，进而在另一个部分里面继续查找的时候，此时就可以使用二分查找算法了

下面具体讲解二分查找算法：

有一个数组，左端点下标为left，右端点下标为right，中间位置的下标为mid，此时要查找的目标值是t，数组的中间值为x

此时选取中间的点x，与目标值t比较会有三种情况：

①x < t ：left = mid +1，接着在 [ left, right ]的区间查找
②x > t ：right = mid - 1，接着在 [ left, right ]的区间查找
③x == t：返回结果mid

循环的条件：left > right时就停止，因为每次判断完，如果没有找到结果，要不就是right左移或left右移，直到移动结束后left > right，就说明遍历结束了

二分查找算法的时间复杂度是O(logN)

代码如下：

class Solution {
public:
    int search(vector<int>& nums, int 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 if(nums[mid] > target) right = mid - 1;
            else return mid;
        }
        return -1;
    }
};

有个细节，在算中间值的下标mid时，没有采用(left + right) / 2来计算，因为这种计算方式有可能会导致溢出的风险，因为如果left和right都是极大的数，这两个数相加就可能会导致溢出

因此在这里采用(right - left) / 2，计算出left和right之间的距离的一半，再与left相加，就不会有上述风险了

朴素的二分模版

        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if(......) 
                left = mid + 1;
            else if(......) 
                right = mid - 1;
            else 
                return ......;
        }

题目二：在排序数组中查找元素的第⼀个和最后⼀个位置

给你一个按照非递减顺序排列的整数数组 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]

解法一：暴力解法

同样在遇到这个题时，最容易想到的就是暴力解法了，依旧是遍历数组，在找到的第一个位置处做标记，在找到的最后一个位置处做标记，最后返回，如果没有找到要求的数，就返回[-1, -1]

暴力查找的时间复杂度依旧是O(N)

解法二：朴素二分

这个朴素二分的方法，在这道题中，就明显不太适用了，因为如果一个数组全部是同一个数，那么我使用朴素二分，从中间去一个点，并不能确定剩下符合条件的数是在左边还是右边，所以还是需要向左和右继续找，这样的时间复杂度和暴力解法并没有区别

所以下面详细说明一下查找区间的左端点和右端点的情况：

查找区间左端点

有一个数组如下所示，目标值t等于3，此时需要查找区间的左端点，也就是第一个3出现的位置

所以需要利用二段性，将数组划分为上图所示的两部分，小于t和大于等于t这两部分

有一个数组，左端点下标为left，右端点下标为right，中间位置的下标为mid，此时要查找的目标值是t，数组的中间值为x

与朴素的二分模版不同，此题的target可能不止一个数，所以中间值与目标值t的比较就有如下两种情况：

①x < t：left = mid + 1，接着在 [ left, right ]的区间查找
②x >= t：right = mid，接着在 [ left, right ]的区间查找

需要注意，当x < t时，因为此时mid所指向的x都是不满足题意的，所以left需要移动到mid的右边，所以是 left = mid + 1

而当 x >= t时，此时的x有可能是目标值，所以right不能像二分的朴素模版那样，移动到mid的左边，而是移动到mid的位置

下面详细说明二分的两个细节：循环条件和求中点的操作

循环条件的相关细节：

关于循环条件：这里选的是 left < right 就进入循环，而不是left <= right

分下面三种情况讨论，来说明为什么循环条件选择 left < right

①数组中有结果：
数组如下，最终结果在ret这个位置开始：

最开始的时候，left是处于不合法的区间，而right是处于合法的区间，left区间和right区间如下所示：

right一直在合法区间上移动的时候，是绝对不会超过ret这个点的，因为right永远执行的是right = mid这个操作
而left是永远想跳出这个不合法区域的，因为left永远执行的是 left = mid + 1这个操作

而当left跳出区域与right相遇后，所指的这个位置正好是最终结果

所以当left = right的时候，就是最终结果了，无需继续判断

②数组全大于t：

如果全是大于t的，那么right是只会向左移动，直到移动到left的位置为止，因为这种情况下，left永远都不会移动，只有right不停地执行right = mid这个操作

此时left和right相遇了，但是这种情况下是没有最终结果的，所以只需判断一下相遇位置的值是否等于t即可，如果相等就返回这个位置的值，如果不相等就返回[-1, -1]即可

所以当left = right的时候，只需再与t比较一次判断是否是左端点的值即可，无需继续进入循环判断

③数组全小于t：

如果全是小于t的，那么left是只会向右移动，直到移动到right的位置为止

当他们相遇时，同样只需判断一下相遇位置的值是否等于t即可

所以当left = right的时候，只需再与t比较一次判断是否是左端点的值即可，无需继续进入循环判断

通过上述的三种情况，证明了循环条件是 left < right，不需要=，因为相等的时候就已经得出最终结果了，没有必要再进入循环中判断了

如果我们的循环条件不是 left < right，而是写成了 left <= right，就会出现死循环的情况

因为如果是第一种情况，left和right都指向了ret的位置，此时继续判断，right依旧是指向该位置，并不发生改变，继续进入循环......从而导致死循环

求中点的操作的相关细节：

在第一题中使用的朴素的二分模版，求中点时，采用的公式是：mid = left + (right - left) / 2

其实还有一个公式也可以求中点：mid = left + (right - left + 1) / 2

区别就是在括号中 +1，那么这两个的区别是什么呢？

很简单，当数组个数是偶数时，例如共有6个数，第一种公式求出来是下图这个位置：
mid = 0 + (5 - 0) / 2 = 2

如果是第二种公式，求出来则是这个位置：
mid = 0 + (5 - 0 + 1) / 2 = 3

可以观察到，在数组个数是偶数时，中间位置是两块，第一个公式指向的是偏左的那一块位置，而第二个公式指向的则是偏右的那一块位置

这两种情况再朴素二分中都可以使用，而在这种情况下则会有问题

当最后一个left和right指向下图所示的情况时：

如果采用第二个公式，计算出来mid指向中间偏右的位置，即：

如果是x < t，那么left = mid + 1，此时再判断不满足循环条件left < right，循环就会终止
而如果是x >= t，那么right = mid，此时mid和right指向同一块位置，这时就会出现死循环的情况

因此得出结论，在求区间左端点时，使用第二个公式求中点，就会陷入死循环

而如果采用第一个公式计算中点，mid就会指向：

如果是x < t，那么left = mid + 1，此时left和right相遇，循环终止
而如果是x >= t，那么right = mid，此时left和right同样相遇，循环终止

不会出现上述死循环的情况

查找区间右端点

同样是该数组如下所示，目标值t等于3，此时需要查找区间的右端点，也就是最后一个3出现的位置：

所以需要利用二段性，将数组划分为上图所示的两部分，小于等于t和大于t这两部分

有一个数组，左端点下标为left，右端点下标为right，中间位置的下标为mid，此时要查找的目标值是t，数组的中间值为x

①x <= t：left = mid，接着在 [ left, right ]的区间查找
②x > t：right = mid - 1，接着在 [ left, right ]的区间查找

当x <= t时，表示结果就在mid的左边这个区域，此时的x有可能是目标值，所以left不能像二分的朴素模版那样，移动到mid的右边，而是移动到mid的位置
当x > t时，因为此时mid所指向的x都是不满足题意的，所以right需要移动到mid的左边，所以是 right= mid + -1

下面详细说明二分的两个细节：循环条件和求中点的操作

循环条件的相关细节：

循环条件同样是left < right

具体证明和上面求左端点的步骤一样，以此类推

求中点的操作的相关细节

求中点的方式依旧是这两个公式

①mid = left + (right - left) / 2
②mid = left + (right - left + 1) / 2

第一个公式求的是靠左的，第二个公式求的是靠右的

当最后一个left和right指向下图所示的情况时：

如果采用第一个公式，计算出来mid指向中间偏左的位置，即：

如果是x <= t，那么left = mid，此时mid和right指向同一块位置，这时就会出现死循环的情况

因此得出结论，在求区间右端点时，使用第一个公式求中点，就会陷入死循环

而如果采用第二个公式计算中点，mid就会指向中间偏右的位置：

如果是x <= t，那么left = mid，此时left和right相遇，循环终止
而如果是x > t，那么right = mid - 1，此时left和right同样相遇，循环终止

不会出现上述死循环的情况

利用上述讲解的计算左端点和右端点的方法，解决此题：

代码如下：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size() == 0) return {-1,-1}; //判断边界条件
        int left = 0, right = nums.size()-1,begin = 0;
        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; //begin存储左端点的下标

        left = 0, right = nums.size()-1;
        while(left < right) //计算右端点
        {
            int mid = left + (right -left + 1) / 2;
            if(nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        return {begin,right};        
    }
};

查找区间左端点二分模版

        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(......) left = mid;
            else right = mid - 1;
        }

题目三：搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 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

这道题也可以很容易的看出这个数组的二段性

也就是所插入的值要不和数组中的数相等，要不就是第一次出现比它大的这个数的位置，所以可以得到结论：最终找到的位置应该是大于等于目标值target的

所以利用二段性分为小于target，和大于等于目标值target

代码如下：

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

题目四：x的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

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

解法一：暴力解法

依次列举1、2、3、4、5....的平方，与x做比较，如果比x小就继续往后试，直到找到这个数的平方要么是大于这个数，要么是等于这个数位置，就说明找到了最终解

当等于时就返回这个数，当是大于时就返回它前一个数

解法二：二分查找

二分查找最重要的就是找到二段性

我们可以发现，整个数组可以分为小于等于x和大于x这两个区域

所以就有两种情况：

①mid * mid <= x：left = mid
②mid * mid > x：right = mid - 1

分情况讨论即可

代码如下：

class Solution {
public:
    int mySqrt(int x) {
        if(x < 1) return 0; // 处理边界条件
        long long left = 1, right = x;
        while(left < right)
        {
            long long mid = left + (right - left + 1) / 2;//防溢出
            if(mid * mid <= x) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

题目五：山峰数组的峰顶

符合下列属性的数组 arr 称为 山脉数组 ：

arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
- arr[0] < arr[1] < ... arr[i-1] < arr[i]
- arr[i] > arr[i+1] > ... > arr[arr.length - 1]

给你由整数组成的山脉数组 arr ，返回满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。

你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

示例 1：

输入：arr = [0,1,0]
输出：1

示例 2：

输入：arr = [0,2,1,0]
输出：1

示例 3：

输入：arr = [0,10,5,2]
输出：1

这个题目也是比较好理解的，所给的数组元素的大小，都是先上升再下降的，都存在一个最大值，求这个最大值的下标

解法一：暴力枚举

从前往后依次枚举，当枚举到一个数的值是大于前一个数的，这个数就是峰值，返回下标即可

暴力解法的时间复杂度是O(N)

解法二：二分查找算法

此时根据这个峰值数组的特性，可以找到这个数组的二段性，如下图所示：

左边的区间包含峰值，每一个数都大于前一个数

右边区域不包含峰值，每一个数都小于小于前一个数

代码如下：

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

题目六：寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

这道题需要注意的是：nums[-1] = nums[n] = -∞ 这个条件

表示默认第一个元素前和最后一个元素之后都是最小的，所以如果是如下这种情况，最后一个位置也是峰值，如下：

或是这种情况，第一个也是峰值：

这就是刚买这个条件所表达的意思

解法一：暴力枚举

从第一个位置开始暴力枚举，分下面的情况讨论即可：

①第二个数比第一个小，此时第一个数就是峰值
②在走的过程中一直上升，直到遇到一个比该值小的，此时该值就是峰值
③从第一个数开始一直上升，直到最后一个数为止，此时最后一个数是峰值

暴力枚举的时间复杂度是O(N)

解法二：二分查找算法

在arr数组中，有两种情况，一个坐标是i另一个坐标是i+1

如果arr[i] > arr[i+1]，说明此时是下降趋势，也就是说答案就在 <= i的区域，此时需要改变right的值

如果arr[i] < arr[i+1]，说明此时是上升趋势，也就是说答案就在 > i的区域，此时需要改变left的值

将上述所说的i替换为mid，就可以使用二分查找算法进行计算了

代码如下：

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

题目七：搜索旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

需要注意数组中的数是互不相同的，需要找出最小元素

解法一：暴力枚举

暴力枚举，遍历一遍数组，找出最小的元素

时间复杂度O(N)

解法二：二分查找算法

此题也可以找到数组的二段性，每一个数组都大致可以分为下面这种情况，即原本的递增数字旋转后，会出现先递增，再递增的趋势：

AB这一段都大于D点，CD这一段都小于等于D点，就有了二分查找算法所需的二段性

设D点为x，分为下面两种情况：

①arr[mid] > x，表示在AB线段上，此时改变需要改变左区间
②arr[mid] <= x，表示在CD线段上，此时改变需要改变右区间

代码如下：

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

题目八：0〜n-1中缺失的数字

某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。

示例 1:

输入: records = [0,1,2,3,5]
输出: 4

示例 2:

输入: records = [0, 1, 2, 3, 4, 5, 6, 8]
输出: 7

这里的最后一道题，其实是很简单的，其中是有非常多的解法的，具体如下：

前四种的时间复杂度都是O(N)，因为都需要遍历一遍数组

解法一：遍历数组

因为是学号从0开始递增的，所以直接遍历数组，看哪个数断开了

代码如下：

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

解法二：哈希表

建立大小为n的哈希表，遍历原始数组，填进哈希表中，接着遍历哈希表，发现哪个数字没有填，答案就是那个数字

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int i = 0;
        unordered_map<int, int> ump; 
        for (auto& it : records) ump[it]++;
        for (i = 0; i < records.size(); i++) 
        {
            if(!ump.count(i)) break;
        }
        return i;
    }
};

用数组替代哈希表：

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int i = 0;
        int hash[10000] = {0};
        for (auto& it : records) hash[it]++;
        for (i = 0; i < records.size(); i++) 
        {
            if(hash[i] == 0)
                break;
        }
        return i;
    }
};

解法三：位运算(异或运算)

异或运算时有个特点：相同为0，相异为1，所以我们可以先把数组中的元素异或一遍，再异或n个递增的数组，异或完后剩下来的就是缺失的数

因为缺失了一个数，所以for循环中个数需要加1

代码如下：

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int i = 0, res = 0;
        for (auto& it : records) res ^= it;
        for (i = 0; i < records.size()+1; i++) res ^= i;
        return res;
    }
};

解法四：数学(高斯求和公式)

也就是将n个数加起来，依次减去原数组中的数，剩下的就是缺失的数

因为n个数从0开始递增，所以公差是1，可以使用(首项 + 末项) * 项数 / 2计算

因为从0开始，共有n个数，所以首项是0，末项是records.size()也就是n，因为假设有3个数，末项是2，而records中缺少了一个数，records.size()就为2，所以可以将records.size()当做末项

项数是n+1，因为n是records.size()，而records缺少了一个数，所以项数需要+1

代码如下：

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int i = 0, res = 0, n = records.size();
        res = (0 + n)*(n + 1)/2;
        for (i = 0; i < records.size(); i++) res -= records[i];
        return res;
    }
};

解法五：二分查找算法

这道题光看数字可能看不出来怎么使用二分，而如果将下标都标注出来，此时就可以很清晰的看出二段性了，假设数组是0,1,2,3,5，如下所示，黑色的表示数字元素，红色的表示下标：

可以很清晰的看到，绿框中元素与所对应的下标是相等的，而紫框中的元素与下标是不同的，这里就体现了二段性，我们要找的就是下标为4的这个位置

①arr[mid] == mid，表示此时在绿框中，需要改变left，即left = mid + 1
②arr[mid] != mid，表示此时在紫框中，需要改变right，并且mid可能是答案，所以right = mid

需要注意边界情况，如果数组是0,1,2,3,4这样的类型，缺了一个5，此时我们按照上述的情况使用二分查找算法，会使得最终的left指向4这个值的下标，所以我们需要最后比较一下，left所对应的值和left是否相等，如果相等就表示是这种特殊情况，需要进行特殊处理

代码如下：

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int left = 0,right = records.size()-1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(records[mid] == mid) left = mid + 1;
            else right = mid;
        }
        //处理细节
        return records[left] == left ? left + 1 : left;
    }
};

二分查找题目到此结束