【优选算法篇】：揭开二分查找算法的神秘面纱--数据海洋中的精准定位器

✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：c++篇–CSDN博客

一.二分查找算法

• 基本思想

  二分查找算法的基本思想是：首先确定目标值可能存在的区间，然后逐步缩小区间直到确定目标值的位置或者确定目标值不存在。这个过程中，每次都会将查找范围缩小一半，因此大大提高了查找效率。

• 前提条件

  有些地方可能对于二分查找算法的前提条件要求必须是有序的待查找数组，如果数组无序则不能使用二分查找。但实际上并不是“必须有序”才能使用，只要待查找数组满足二段性，可以将数组分成两个区间，这两个区间中的子数组又是有序的，同样可以使用二分查找，在后面的一些例题中就有这样的使用。

• 算法步骤

  这里不具体讲解，直接在后面通过模板来讲解

• 时间复杂度和空间复杂度

  • 时间复杂度：二分查找算法的时间复杂度为O(log n)，其中n是数组的长度。因为每次查找都会将范围缩小一半，所以查找的次数是log n(以2为底数的对数)。
  • 空间复杂度：因为只使用几个额外的变量（通常是left,right,mid)，所以空间复杂度是O(1)。

二.算法模板

模板一

这里通过一道例题来引出模板一：朴素二分查找

题目：

算法原理及模板一：

代码实现：

int search(vector<int>& nums,int target){
    //朴素二分查找
    int left = 0, right = nums.size() - 1;
    int mid = 0;

    while(left<=right){
        //获取中间值
        //两种写法
        mid = left + (right - left) / 2;
        //mid = left + (right - left + 1) / 2;

        if(nums[mid]<target){
            left = mid + 1;
        }
        else if(nums[mid]>target){
            right = mid - 1;
        }
        else{
            return mid;
        }
    }

    return -1;
}

模板二

这里通过一道例题来引出模板二以及模板三

题目：

算法原理及模板二：

模板三

算法原理及模板三：

代码实现：

vector<int> searchRange(vector<int> &nums, int target)
{
    // 处理特殊情况，空数组
    if (nums.empty())
    {
        return {-1, -1};
    }
    int left = 0, right = nums.size() - 1;
    int mid = 0;
    int begin = 0;

    // 查找区间的左端点
    // 细节点一：这里只能左指针小于右指针，不能等于
    while (left < right)
    {
        // 细节点二：获取中间值这里不能加一
        mid = left + (right - left) / 2;

        if (nums[mid] < target)
        {
            left = mid + 1;
        }
 
        if (nums[mid] >= target)
        {
            right = mid;
        }
    }

    // 查找左端点结束后，找到继续查找右端点，否则返回没有找到
    if (left == right && nums[left] == target)
    {
        begin = left;
    }
    else
    {
        return {-1, -1};
    }

    right = nums.size() - 1;

    // 查找区间的右端点
    // 细节点一
    while (left < right)
    {
        // 细节点二：获取中间值这里要加一
        mid = left + (right - left + 1) / 2;

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

        if (nums[mid] > target)
        {
            right = mid - 1;
        }
    }

    return {begin, right};
}

三.例题演练

1.x的平方根

题目：

算法原理：

从1到x的数组中：[0，x-1]（【1，2，3…x】），因为返回的是整数，对于小数部分要舍去，因此要往小的数进位，比如2.82842，进位到2而不是3，所以根据二段性可以分为两个区间：假设目标值下标为s，[0，s]区间中的值的平方都小于等于x，（s，x-1]区间中的值的平方都大于x，使用模板三。

代码实现：

int mySqrt(int x) {
    if(x<1){
        return 0;
    }

    int left=1,right=x;
    long long mid=0;

    while(left<right){
        mid=left+(right-left+1)/2;

        if(mid*mid<=x){
            left=mid;
        }
        else{
            right=mid-1;
        }
    }

    return left;
}

2.搜索插入位置

题目：

算法原理：

因为可能存在目标值不存在的情况，所以不能使用朴素二分查找模板，这里只能使用模板二或者模板三，这里以模板三为例。

根据二段性可以将数组分为两个区间，假设目标值下标为s，[0，s]区间的值小于等与目标值，(s，n-1)区间的值大于目标值。

当出现目标值不存在的情况时，找到的一定是小于目标值的下标位置，直接返回该位置的下一个即可。

代码实现：

int searchInsert(vector<int>& nums,int target){
    int left=0,right=nums.size()-1;
    int mid;

    while(left<right){
        mid = left + (right - left + 1) / 2;

        if(nums[mid]<=target){
            left = mid;
        }
        else{
            right = mid - 1;
        }
    }

    if(nums[left]<target){
        return left+1;
    }
    return left;
}

3.山脉数组的峰值索引

题目：

算法原理：

在这道题中，如果第一眼看数组不是有序的，可能就会觉得不能使用二分查找算法来解，但是，我们仔细观察可以发现，在这道题中，根据题目要求可以将数组分成两端，也就使数组具有二段性，因此这道题实际上还是使用二分查找算法来解。

假设峰值是s，s左边的值[0，s)全都有序，也就是升序排列，前一个值小于后一个值，而s右边的值(s，n-1]也全都有序，但是是降序排列，前一个值大于后一个值。

根据二段性就可以使用模板，这里用模板三来演示。

代码实现：

int peakIndexInMountainArray(vector<int>& arr){
    int left = 0, right = arr.size() - 1;
    int mid = 0;

    while(left<right){
        mid = left + (right - left + 1) / 2;

        if(arr[mid-1]<arr[mid]){
            left = mid;
        }
        else{
            right = mid - 1;
        }
    }

    return left;
}

4.寻找峰值

题目：

算法原理：

这道题和上面的山脉数组的峰值算法原理一样，同样可以使用相同的模板来解。唯一不同的是，这道题中的数组可能有多个峰值，但我们只需找到一个返回即可。

代码实现：

int findPeakElement(vector<int>& nums){
    int left = 0, right = nums.size() - 1;
    int mid=0;

    while(left<right){
        mid = left + (right - left + 1) / 2;

        if(nums[mid-1]<nums[mid]){
            left = mid;
        }
        else{
            right = mid - 1;
        }
    }

    return left;
}

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

题目：

算法原理：
在这道题中，给定的数组同样不满足有序的条件，但是根据题意可以发现，数组满足二段性。

假设最小值下标为s，最大值左边区间的值[0,s)，全都小于最大值；最小值右边区间的值[s，n-1]全都小于数组第一个值（下标为0)；因为数组第一个值在左边区间中是最小的，左边区间的值又全都大于右边区间的最后一个值（下标为n-1)，也就是数组最后一个值。

根据二段性可以使用模板二或者模板三，使用不同的模板时，要处理不同的细节。

使用模板二，就是以最后一个元素作为区分值，最小值左边元素都大于最后一个元素，最小值右边都小于等于最后一个元素，直接找最小值。

使用模板三，就是以第一个元素为区分值，最小值元素左边都大于等于第一个元素，最小值右边都小于第一个元素，找最大值，最小值就是最大值后一个，因此循环结束后，还要将下标再加一才是最小值的下标。

代码实现：

int findMin(vector<int>& nums){
    int left = 0, right = nums.size() - 1;

    //利用二段性,以最后一个元素为区分值
    //最小值左边元素都大于最后一个元素，最小值右边都小于等于最后一个元素
    //直接找最小值
    while(left<right){
        int mid = left + (right - left) / 2;

        if(nums[mid]>nums[nums.size()-1]){
            left = mid + 1;
        }
        else{
            right = mid;
        }
    }

    //以第一个元素为区分值
    //最小值元素左边都大于等于第一个元素，最小值右边都小于第一个元素
    //找最大值，最小值就是最大值后一个
    while(left<right){
        int mid = left + (right - left + 1) / 2;

        if(nums[mid]>=nums[0]){
            left = mid;
        }
        else{
            right = mid - 1;
        }
    }
    if(left!=nums.size()-1){
        left++;
    }
    
    
    return nums[left];
}

6.点名（0到n-1中缺失的数字）

题目：

算法原理：
这道题相当于从0当n-1中，查找缺失的数字，仔细看我们可能看不出来有什么二段性质，但是如果我们将每个值都和下标对比，就是发现二段性。

这里以缺失数字4的数组为例：

​ 【0，1，2，3，5，6】

下标：【0，1，2，3，4，5】

从上面我们可以看出，缺失数字的下标左边区间的下标对应数组中的数字，而缺失数字右边区间的下标则是对应数字减一。

根据上面的二段性就可以使用模板二。

注意还有一种情况可能是：【0，1，2，3】数组有序，这时缺失的数字就是4，因此在循环结束后，要进行一个判断，如果当前下标是最后一个，且下标对应数组中的数字，这时下标要加一返回。

代码实现：

int takeAttendance(vector<int>& nums){
    int left = 0, right = nums.size() - 1;

    while(left<right){
        int mid = left + (right - left) / 2;

        if(nums[mid]==mid){
            left = mid + 1;
        }
        else{
            right = mid;
        }
    }

    if(left==nums.size()&&nums[left]==left){
        left++;
    }

    return left;
}

以上就是关于二分查找算法以及例题的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！