专题三——二分算法

原理

模板

朴素二分算法

非朴素二分算法

一二分查找

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

三点名

四x的平方根

五搜索插入位置

六山脉数组的峰顶索引

七寻找峰值

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

原理

定义两个指针：left指向数组第一个元素，right指向数组的最后一个元素；通过某种条件的判断，让left与right向之间靠拢；最终left与right所指的元素来确定最后的答案

模板

二分算法的实现有两个模板：朴素二分算法与非朴素二分算法

朴素二分算法

while(left <= right)
{
    int middle = left+(right-left)/2 //写成(right-left)/2有越界的风险
    if(...)
    {
        left =middle + 1; 
    }
    else
    {
        right = middle - 1;
    }

}

非朴素二分算法

//左端点
while(left < right) //left <= right会越界
{
    int middle = left + (right - left) / 2;//left +(right - left + 1) /2会死循环
    if(...)
    {
        left = middle + 1;
    }
    else
    {
        right = middle;
    }

}

//右端点
while(left < right) //left <= right会越界
{
    int middle = left + (right - left +1) / 2;
    if(...)
    {
        left = middle;
    }
    else
    {
        right = middle - 1;
    }

}

大部分情况的二分算法题用的都是非朴素二分算法模板来实现的！

一二分查找

oj链接：704. 二分查找 - 力扣（LeetCode）

思路：懂了模板直接套用朴素二分算法解决：

当nums[middle] < target ; left=middle + 1；else right = middle - 1

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

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

oj链接：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

朴素二分算法解决不了，用非朴素二分模板来解决：

题目要求第一个与最后一个位置，直接用两个非朴素模板求出与target相同的左右两个端点

class Solution 
{
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        //越界判断
        if(nums.size() == 0) return {-1 , -1};
        //开始元素下标(求左端点)
        vector<int> ans(2);
        int left = 0 , right = nums.size() - 1;
        while(left < right)
        {
            int middle = left + (right - left) / 2;
            if(nums[middle] < target) left = middle + 1;
            else right = middle;
        }
        //有可能没有target 
        if(nums[left] != target) return {-1 , -1};
        ans[0] = left;
        //最后元素下标(求右端点)
        //有的话在left的右边，left不用再次走到开始位置
        right = nums.size() -1;
        while(left < right)
        {
            int middle = left +(right - left +1) /2;
            if(nums[middle] <= target) left = middle;
            else right = middle -1;
        }
        ans[1] = right;
        return ans;
    }
};

三点名

oj链接：LCR 173. 点名 - 力扣（LeetCode）

思路：此题的思路有很多：等差数列求和，哈希表，异或...

但这道题给出的条件适合来用二分算法解决：

判断数值与下标是否对应来进行left与right的移动

class Solution {
public:
    int takeAttendance(vector<int>& records) 
    {
        int left=0,right=records.size()-1;
        while(left<right)
        {
            int middle=left+(right-left)/2;
            if(middle==records[middle]) left=middle+1;
            else right=middle;
        }
        //有可能数组里面与下标都对应上了返回后一个数字->[0,1]
        if(records[left]==left) return left+1;
        return left;
    }
};

四x的平方根

oj链接：LCR 072. x 的平方根 - 力扣（LeetCode）

思路：从[1，x]中来找出符合某数的平方根<=x：如果在里面的某个值的平方根>x的，说明目标值是在这个值的左边区域，缩小范围更新right的值:是要等于它还是在它前一个位置就要自己来画图分析了；最后用非朴素模板套进去就解决本道题的求

五搜索插入位置

oj链接：LCR 068. 搜索插入位置 - 力扣（LeetCode）

思路：套用非朴素模板解决，注意最后结果的处理

class Solution 
{
public:
    int searchInsert(vector<int>& nums, int target) 
    {
        int left = 0,right = nums.size() - 1;
        while(left < right)
        {
            int middle = left +(right -left)/2;
            if(nums[middle] < target) left = middle + 1;
            else right = middle;
        }
        //left与right走到数组最后的处理
        if(right == nums.size() - 1 && nums[right] < target) return right + 1;
        else return right;
    }
};

六山脉数组的峰顶索引

oj链接：LCR 069. 山脉数组的峰顶索引 - 力扣（LeetCode）

思路：山脉数组将数组分为两个区间：

左半边是递增的：arr[i] > arr[i-1]（包含峰值）；右半边是递减的：arr[i] < arr[i-1]（不包含）

有了这个二段性，我们就可以来利用二分算法来解决问题，使得最后left与right指向峰顶

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) 
    {
        int left = 0,right = arr.size() - 1;
        while(left < right)
        {
            int middle = left + (right - left + 1) / 2;
            //middle在左半区间
            if(arr[middle] > arr[middle - 1]) left = middle;
            //middle在右半区间
            else if(arr[middle] < arr[middle -1]) right = middle -1;
        }
        return left;
    }
};

七寻找峰值

oj链接：162. 寻找峰值 - 力扣（LeetCode）

思路：要找数组其中一个峰值转化为求数组的峰值，与上面思路是一样的！

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

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

oj链接：153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

思路：将旋转数组分为两段；AB段前n(旋转的次数)个数值；CD是剩余的个数；我们来拿最后一个元素(nums[n - 1])作参照物，有这样的一个规律：

AB段的值nums[i]一定>nums[n - 1];CD段的值nums[j]<=nums[n - 1];

有了二段性，我们就可以用二分算法来解决问题，只需来判断left与right的移动就完成

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