算法练习——二分算法

学前须知：

👉：二分算法的核心在于：能够正确找到数据的二段性(其中一段有目标值，另一段没有)

👉：二分算法的另一个核心在于边界条件的取舍，这关系到整个代码是否会陷入死循环

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

题目要求：

解题思路：

二分算法的关键在于：如何找到那个能够将数据分成两段，并逐步缩小范围，最终得到想要的答案。

本题思路：用两次二分算法分别确定左下标和右下标，完成题解。

有关二分算法的知识补充——当只有两个数据时（偶数）

👉：mid = left + (right -left)/2 得到是左边数据

👉：mid = left + (right -left+1)/2得到是右边数据

小贴士(规律)：

凡是 right = mid - 1   则 mid = left + (right -left+1)/2

否则 mid = left + (right -left)/2

二分查找(以找到左下标为例)：

问：怎么做才能得到左边的下标呢？

答：前面我们提到，二分算法的目的是能够将数据分成两段，其中一段有我们想要的数据，而另一端没有，因此可以将另一端完全排除。定义left 和 right 分别指向数组左端点和右端点。mid根据查找的下标为左还是右决定。此处mid = left + (right -left)/2

问：那该如何排除我们不想要的数据呢？

答：我们来看看示例一，题目有两个数据满足我们的要求，如果要按上述将数据分成有用段和无用段那么只有两种方法(数据是连续的)，要么排除所有比8大的，要么排除所有比8小的，因为我们要的是左下标，因此排除比8小的

问：为什么排除所有比8小的，能够得到左下标，而排除所有比8大的，能得到右下标？

答：

        当 nums[mid] < 8 时，此时 mid 落在了左端部分，因为左端部分所有数都比 8 小，所以left = mid + 1，此时 left 下标处的值满足两种情况 1、小于 target； 2、等于target 

        当 nums[mid] ≥ 8 时，此时mid 落在了右端部分，则 right = mid，此时right也有两种情况 1、大于 target； 2、等于target

☆☆☆注 ：右端部分的target可能是多个 target 中的任意一个，不满足我们所要的最左端，因此从这里就能看出，为什么排除所有比8小的，才能的到最左端下标。 同理找右下标

细节：外循环的结束条件(left < right)

问：取不取等号？

答：不取，如图所示(找左下标时)

分析：按照上面的步骤最终我们可以得到上图，此时nums[mid] = 8 ,因为找的是左下标，所以此时 left 不同，right = mid，得到下图：

若取等号再次进入循环，则 mid == 8 ，right == left 进入死循环，因此不能取等号。 

总结：

👉：每次二分的点只有一个，但是一组数据可能用到多次二分算法来确定最终结果

👉：二分算法的难点在于处理边界问题，稍有不慎就有可能陷入死循环

代码实现：

vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        if(n == 0){
            return {-1,-1};
        }
        int left = 0, right = n-1;
        while(left < right)
        {
            int mid = left + (right - left)/2;
            if(nums[mid] < target){
                left = mid + 1;
            }
            else{
                right = mid;
            }
        }
        int tmp = -1;
        if(nums[left] == target){
            tmp = left;
        }

        left = 0 , right = n-1;
        while(left < right)
        {
            int mid = left + (right - left + 1)/2;
            if(nums[mid] > target){
                right = mid - 1;
            }
            else{
                left = mid;
            }
        }
        if(nums[left] == target)
        {
            return {tmp,left};
        }
        else
        {
            return {-1,-1};
        }
    }

二：x的平方根

题目要求：

解题思路：

以示例2为例：

思路：

按照上述思路执行时，最终会来到如图所示的结果，此时 left = right 跳出循环， left 所在位置即为最终答案

代码实现：

 int mySqrt(int x) {
        long long left = 0, right = x;
        while(left < right)
        {
            long long mid = left + (right-left+1)/2; //避免数据溢出
            if(mid*mid > x)
            {
                right = mid - 1;
            }
            else
            {
                left = mid;
            }
        }
        return left;
    }

三：寻找山峰值

题目要求：

解题思路：

以下述图片为例：
寻找数据二段性是解题关键。

该数据段的特点是：某一段的数据是递增，有一段是递减，

即某一段 nums[n] < nums[n+1]，另一段 nums[n] > nums[n+1]

于是我们便可以通过比较 nums[n]与nums[n+1] 的大小关系来判断当前处于哪一段上

👉：当 nums[n] < nums[n+1]时，n+1 左端的数据可以全部舍去，因此 left = mid + 1

👉：当 nums[n] ≥ nums[n+1]时，n 对应位置处可能刚好是目标值，因此 right = mid

代码实现：

   int peakIndexInMountainArray(vector<int>& arr) {
        int n = arr.size();
        int left = 0,right = n - 1;
        while(left < right)
        {
            int mid = left + (right - left)/2;
            if(arr[mid] < arr[mid+1])
            {
                left = mid + 1;
            }
            else
            {
                right = mid;
            }
        }
        return left;
    }

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

题目要求：

解题思路：

个人见解：

这道题不像前面三道二段性那么好找，做了这道题之后，对于博主而言，二分算法还有一个容易忽视的地方，那就是：如何找到正确的参考点！

第一、二中的参考点是题目给的，第三问的参考点是mid位置处的下一个或者是上一个位置处的数据，但是这题的参考点并非一、二、三问那样。

之前我们都是在数组中去观察数据，这道题当中，我们不妨换一个角度去看问题，首先明确这段数据的变化规律是：一段有序的数组，将他的尾部数据依次从后向前插入到头部，整个数据被分成两段递增的数据段，且没有重复的数据。

以示例2为例：

我们可以得到如下图片。

上面我们说了，直接观察数组中的数据很难发现二段性，我们不妨如下绘制图片

以数组末尾数据2为参考点，可以发现：

👉：当nums[mid] > 2 时，说明此时 mid 落在左上角处，这里没有我们想要的答案

👉：当nums[mid] ≤ 2 时，说明此时 mid 落在右下角处，这里有我们要的答案

当我们弄清楚数据的二段性时，再回到数组，想想 left 和 right 的更新方式。

👉：当 mid 位置处的数据 > 2 ，那么此时 mid+1 左侧的数据都大于 2，因此 left=mid+1

注：别忘了这原本就是从一个有序数组变过来的，首端数据是大于末端数据的！

👉：当 mid 位置处的数据 ≤ 2 ，那么此时 mid 左侧包含 mid 可能存在答案，因此 right=mid

代码实现：

    int findMin(vector<int>& nums) {
        int n = nums.size();
        int left = 0,right = n - 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中缺失的数字

题目要求：

解题思路：

以示例2为例，我们可以得到如下图片：

仔细观察不难发现：假设缺失的数字为 x，那么x前面的数字都和下标相等，而x后的数字都大于下标，因此左右指针有这样的更新条件：

👉：当 num[i] == i 时，缺失的数字不可能在 i 的左侧，包括i，那么 left = mid + 1；

👉：当 num[i]  > i 时， 缺失的数字可能不在i的右侧，也可能刚好是 i，那么right = mid；

这道题还有一个边界问题需要考虑，我们来看以下这个情况(缺失数字为8，不在数组中)：

当我们按着上述的思路，最后一步会执行到如图所示处，此时跳出循环，但是left并非目标值，因此还需多做一步判断:

👉：若arr[left] = left，说明此时缺失值不在数组中，而在下一个位置。

👉：若arr[left] != left，说明当前位置即为缺失值。

代码实现：

    int takeAttendance(vector<int>& records) {
        int n = records.size();
        int left = 0,right = n-1;
        while(left < right)
        {
            int mid = left + (right - left)/2;
            if(records[mid] == mid)
            {
                left = mid + 1;
            }else
            {
                right = mid;
            }
        }
        if(records[left] == left)
        {
            return left+1;
        }
        else
        {
            return left;
        }
            
    }