> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。> 目标：熟练掌握二分查找算法
> 毒鸡汤：学习，学习，再学习 ! 学，然后知不足。
> 专栏选自：刷题训练营
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言分析
最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考：
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
而今天我们的板块是二分查找。
⭐知识讲解
很多小伙伴们在想二分查找嘛，只有升序或者是降序的数字里面查找，有这个想法的是大错特错的，在一些题目中有些无序也可以使用二分查找，所以说二分查找的知识点没有我们想的那么简单，在二分查找中我们会总结一些模板，这些模板要死记硬背要理解哦，题目选取的很多，大家不要跳过一些题目，有些题目是为后面的题目做铺垫的，望大家可以从头看到尾，这里就简单的总结一些二分查找的知识点：
- 二分查找的时间复杂度：log(N)
- 二分查找的范围：有序的数组或者无序
⭐经典题型
🌙topic-->1
题目链接：1. 二分查找 - 力扣（LeetCode）
题目分析：
在一个有序的数组中查找一个数字 target ，如果存在就返回数组的下标，没有的话就返回-1
算法原理：
- 解法一：
暴力遍历数组，时间复杂度为O(n)。
- 解法二：
采用二分查找，二分算法原理博客，这里如果不会二分查找的小伙伴们大家可以看看这篇博客，这里我们再讲解一下解法二的算法原理。
图解：
细节：
- 防止 mid 超过整形最大值
- 循环的条件是 left <= right
代码演示：
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)
left = mid + 1;
else if(nums[mid] > target)
right = mid - 1;
else
return mid;
}
// 没有返回-1
return -1;
}
};模板总结：
// 定义左右指针
int left = 0,right = nums.size() - 1;
// 循环
while(left <= right) // 细节二
{
// int mid = left + (right - left + 1) / 2 等价
int mid = left + (right - left) / 2;// 细节一
if(....)
left = mid + 1;
else if(....)
right = mid - 1;
else
return ...;
}
🌙topic-->2
题目链接：2.二分查找力扣（LeetCode）
题目分析：
在一个非递归中找一个等于 target 下标，如果没有就返回 {-1，-1}
算法原理：
- 解法一：
暴力遍历数组，时间复杂度为O(n)。
- 解法二：
采用二分查找，二分算法原理博客，这里如果不会二分查找的小伙伴们大家可以看看这篇博客，这里我们再讲解一下解法二的算法原理。
代码演示：
class Solution
{
public:
vector<int> searchRange(vector<int>& nums, int target)
{
// 定义左右指针
int left = 0,right = nums.size() - 1;
// 处理空数组
if(nums.size() == 0)
return {-1,-1};
int begin = 0;// 定义左边界
// 去除左边界的元素
while(left < right) // 细节一
{
int mid = left + (right - left) / 2;
if(nums[mid] < target)
left = mid + 1;// 细节二
else
right = mid;
}
// 判断是否有值
if(nums[left] != target)
return {-1,-1};
else
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;// 细节四
}
// 返回
return {begin,right};
}
};模板总结：
while(left < right)
{
int mid = left + (right - left) / 2;
if(...) left = mid + 1;
else right = mid;
}
while(left < right)
{
int mid = left + (right - left + 1) / 2;
if(...) left = mid;
else right = mid - 1;
}
// 下面出现 -1 的时候，上面就加 +1🌙topic-->3
这道题目就不再讲解的这么细了，具体还得琢磨第二道题目：
题目链接：3.二分查找 - 力扣（LeetCode）
题目分析：
给定一个排序数组（升序）和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
算法原理：
- 解法一：
暴力遍历数组，时间复杂度为O(n)。
- 解法二：
采用二分查找，二分算法原理博客，这里如果不会二分查找的小伙伴们大家可以看看这篇博客，这里我们再讲解一下解法二的算法原理。
代码演示：
class Solution {
public:
int searchInsert(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) left = mid + 1;
else right = mid;
}
// 判断
if(nums[left] < target)
return right + 1;
return right;
}
};🌙topic-->4
这道题目就不再讲解的这么细了，具体还得琢磨第二道题目：
题目链接：4.二分查找 - 力扣（LeetCode）
题目分析：
求 X 的算数平方根，结果保留整数。
算法原理：
- 解法一：
暴力举例1 2 3 .... x，时间复杂度为O(n)。
- 解法二：
采用二分查找，二分算法原理博客，这里如果不会二分查找的小伙伴们大家可以看看这篇博客，这里我们再讲解一下解法二的算法原理。
代码演示：
class Solution {
public:
int mySqrt(int x)
{
// 处理
if(x < 1) return 0;
// 定义两个指针
int left = 1,right = x;
// 循环
while(left <right)
{
// 防止溢出
long long mid = left + (right - left +1) /2;
if(mid * mid <= x) left = mid;
else right = mid -1;
}
return left;
}
};🌙topic-->5
这道题目就不再讲解的这么细了，具体还得琢磨第二道题目：
题目链接：5.二分查找 - 力扣（LeetCode）
题目分析：
有一个山峰数组（数组有递增和递减），返回数组中峰顶的下标。
算法原理：
- 解法一：
暴力遍历数组就可以了，时间复杂度为O(n)。
- 解法二：
采用二分查找，二分算法原理博客，这里如果不会二分查找的小伙伴们大家可以看看这篇博客，这里我们再讲解一下解法二的算法原理。
代码演示：
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;
}
};🌙topic-->6
这道题目就不再讲解的这么细了，这里和第五道题目几乎一样：
题目链接：6.二分查找 - 力扣（LeetCode）
题目分析：
有一个山峰数组，这个山峰数组有多个山峰，只要返回其中一峰顶就行（返回数组中峰顶的下标）
算法原理：
- 解法一：
暴力遍历数组就可以了，时间复杂度为O(n)。
- 解法二：
采用二分查找，二分算法原理博客，这里如果不会二分查找的小伙伴们大家可以看看这篇博客，这里我们再讲解一下解法二的算法原理。
代码演示：
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;
}
};🌙topic-->7
这道题目就不再讲解的这么细了，具体还得琢磨第二道题目：
题目链接：7. 二分查找- 力扣（LeetCode）
题目分析：
在一个数组中找最小值。
算法原理：
- 解法一：
暴力遍历数组就可以了，时间复杂度为O(n)。
- 解法二：
采用二分查找，二分算法原理博客，这里如果不会二分查找的小伙伴们大家可以看看这篇博客，这里我们再讲解一下解法二的算法原理。
代码演示：
class Solution
{
public:
int findMin(vector<int>& nums)
{
int left = 0, right = nums.size() - 1;
int x = nums[right]; // 标记⼀下最后⼀个位置的值
while (left < right)
{
int mid = left + (right - left) / 2;
if (nums[mid] > x) left = mid + 1;
else right = mid;
}
return nums[left];
}
};🌙topic-->8
这道题目就不再讲解的这么细了，具体还得琢磨第二道题目：
题目链接：8.二分查找 - 力扣（LeetCode）
题目分析：
在一个 0 ~ n-1 数组中找缺少的数字。
算法原理：
- 解法一：
暴力遍历数组就可以了，时间复杂度为O(n)。
- 解法二：
采用二分查找，二分算法原理博客，这里如果不会二分查找的小伙伴们大家可以看看这篇博客，这里我们再讲解一下解法二的算法原理。
代码演示：
class Solution {
public:
int takeAttendance(vector<int>& records) {
int missingNumber(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;
}
return left == nums[left] ? left + 1 : left;
}
}
};🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
