二分算法——优选算法

个人主页：敲上瘾-CSDN博客

个人专栏：游戏、数据结构、c语言基础、c++学习、算法

        本章我们来学习的是二分查找算法，二分算法的应用非常广泛，不仅限于数组查找，还可以用于解决各种搜索问题、查找极值问题等。在数据结构和算法中，它是基础且重要的算法之一。

接下来我准备了三个题来引出并学习该算法，最后来做总结。

目录

一、二分查找

1.题目解析

2.算法原理

3.代码编写

二、查找元素的首末位置

1.题目解析

2.算法原理

3.代码编写

三、寻找峰值

1.题目解析

2.算法原理

3.代码编写

四、总结

一、二分查找

1.题目解析

        该题目要求是给一个元素target然后在升序数组nums中找到该元素的下标，若不存在则返回-1。题目要求简单易懂就不再多讲，这里要注意两个点：(1)、数组是升序的。(2)、需要返回的是元素下标。

2.算法原理

        对于该题最容易想到的解法就是把数组从头到尾遍历一遍，时间复杂度为O(N)。

        解法二：因为这个数组是有序的所以我们可以用二分的思想，首先使用三个指针（这里指的是数组的下标）left，right，mid，其中left和right维护一段区间，把目标值锁定到[left，right]区间内。mid表示区间的中心下标，把区间一分为二。

        接下来锁定target的位置：如果target小于mid下标指向的元素，那么因为数组是升序，所以target一定在区间[left，mid]中，即right更新为mid，然后更新mid（ mid=left+(right-left)/2 ）。              如果target大于mid指向元素，那么target一定在区间[mid，right]中，即把left更新为mid，然后更新mid。重复操作直到left>right。

如下：

该算法的时间复杂度为logN，证明如下：

3.代码编写

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) right=mid-1;
            else if(nums[mid]<target) left=mid+1;
            else return mid;
        }
        return -1;
    }
};

二、查找元素的首末位置

1.题目解析

        该题的题目要求与上一题类似，都是在升序数组中查找元素，不过该题查找的是元素第一次出现的位置和最后一次出现的位置。这里还要求时间复杂度为O(logN)，这里就很明显地提示了该题要使用二分算法。

2.算法原理

        同样的此题可以使用暴力枚举来解决，不过时间复杂度为O(N)，根据上题的经验这里我们还是考虑使用二分法。不过也很容易发现把上面的算法原模原样搬过来是解决不了该道题的，我们只能找到target元素的是无法锁定它第一次出现的位置和最后一次出现的位置。我们可以用以下解法：

左边界查找：

        当mid指向的元素为target的时候，不用返回，而是让right更新为mid，mid指向元素大于target时同样更新right为mid，即可以合并为

        if(nums[mid]>=target)   right=mid;

当mid指向元素小于target时left更新为mid+1，重复该操作就可以把数组右边的target忽略，锁定最左边的target。这里做循环的时候需要注意循环条件不能是left<=rigth，如果是left<=right就可能使mid一直赋值给right从而进入死循环，所以我们使用left<right。

右边界查找：

        当mid指向的元素为target的时候，不用返回，而是让left更新为mid，mid指向元素小于target时同样更新left为mid，即可以合并为

        if(nums[mid]<=target)   left=mid;

当mid指向元素大于target时right更新为mid-1，重复该操作就可以把数组左边的target忽略，锁定最右边的target。这里做循环的时候同样需要注意循环条件只能是left<rigth。

注意：当元素只有两个时使用mid=left+(right-left)/2计算的mid就是第一个元素，那么也就是mid==left，如果mid指向的元素为target时把mid赋值给left（即left=mid）相当于什么也没干，程序同样会进入死循环。所以我们使用mid=left+(right-left+1)/2计算mid。

        以上的两个查找法几乎可以解决所有的二分算法题，可以作为一个模板记忆，在总结部分我会给出模板。

3.代码编写

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;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(nums[mid]>=target) right=mid;
            else left=mid+1;
        }
        if(nums[left]!=target) return {-1,-1};
        int n=left;
        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 {n,left};
    }
};

三、寻找峰值

1.题目解析

该题要求我们返回任意峰值，比如把数组元素抽象成连续的数据如下：

需要返回以上红圈部分的任意一点， 也就是该元素至少要满足它左边的第一个元素和右边的第一个元素都要小于它。

注意：题目给的信息nums[-1]和nums[n]为负无穷，所以不要忽略以下情况：

2.算法原理

        这题同样可以使用暴力枚举，时间复杂度为O(N)，该解法就不再多讲。

        这个题与上两个题有一个很大的区别是该数组并不是有序的，但是没关系该题同样可以使用二分的思想，注意很多人会误认为二分算法只能用在有序的数组中，而事实并不局限于此，只需要找到数据的二段性即可，如该题我们可以这样：

        该方法也就是上一题的右边界查找，当然也可以使用左边界查找的方法，但用朴素的二分查找解决不了该题。

3.代码编写

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

四、总结

1、二分算法并不局限于数组有序，只要找到数据的二段性即可使用二分算法。

2、二分算法模板

2.1.朴素二分模板

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

2.2.左边界查找模板

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

2.3.右边界查找模板

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