【算法笔记】二分算法原理的深度剖析

【算法笔记】二分算法原理的深度剖析

🔥个人主页：大白的编程日记

🔥专栏：算法笔记

前言

哈喽，各位小伙伴大家好！上期我们讲了滑动窗口的算法原理。今天我们来讲二分查找算法。话不多说，我们进入正题！向大厂冲锋！

一.二分查找

1.1题目

• 题目：二分查找
  

1.2朴素二分

如果存在二段性我们就可以快速筛选掉一段不存在答案的区间

1.3细节问题

这里我们要注意循环结束条件和中点的查找。
在我们的朴素二分中中点取左端和右端都是可以的。

1.4代码实现

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;//偶数取左端，+1取右端
            if(nums[mid]<target)
            {
                left=mid+1;
            }
            else if(nums[mid]>target)
            {
                right=mid-1;
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }
};

1.5朴素模版总结

这就是我们的朴素二分模版。具体括号的具体内容结合题目填充即可。？

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

2.1题目

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

2.2思路分析

• 左端点
  
• 左端点细节问题
  
• 右端点
  
• 右端点细节问题
  

2.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;
        int begin,end;
        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};
        }
        begin=left;
        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;
            }
        }
        if(nums[left]!=target)
        {
           return {-1,-1};
        }
        end=right;
        return {begin,end};
    }
};

2.4左右端点二分模板总结

• 左端点
  

• 右端点
  

• 循环条件
  left<right

• 中点操作
  

三.搜索插入位置

3.1搜索插入位置

• 题目：搜索插入位置
  

3.2思路分析

我们只需要查找左端点即可。

3.3代码实现

• 右端点

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

• 左端点‘

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

四.寻找峰值

4.1题目

• 题目：寻找峰值
  

4.2思路分析

4.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])
            {
                left=mid+1;
            }
            else
            {
                right=mid;
            }
        }
        return left;
    }
};

五.寻找旋转数组中的最小值

5.1题目

• 题目：寻找旋转数组中的最小值
  

5.2思路分析

5.3代码实现

• num[0]

class Solution {
public:
    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[0])
            {
                right=mid;
            }
            else
            {
                left=mid+1;
            }
        }
        return nums[left]>nums[0]?nums[0]:nums[left];//特殊处理
    }
};

• num[n]

class Solution {
public:
    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])
            {
                right=mid;
            }
            else
            {
                left=mid+1;
            }
        }
        return nums[left];
    }
};

后言

这就是二分算法的深度剖析。二分算法细节还是挺多的。大家自己好好梳理一下。今天就分享到这，感谢各位的耐心垂阅！咱们下期见！拜拜~