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

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

🔥专栏：算法笔记

---

前言

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

一.二分查找

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

后言

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