> 作者:დ旧言~
> 座右铭:松树千年终是朽,槿花一日自为荣。
> 目标:熟练掌握二分查找算法
> 毒鸡汤:学习,学习,再学习 ! 学,然后知不足。
> 专栏选自:刷题训练营
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言分析
最早博主续写了牛客网130道题,这块的刷题是让同学们快速进入C语言,而我们学习c++已经有一段时间了,知识储备已经足够了但缺少了实战,面对这块短板博主续写刷题训练,针对性学习,把相似的题目归类,系统的刷题,而我们刷题的官网可以参考:
而今天我们的板块是二分查找。
⭐知识讲解
很多小伙伴们在想二分查找嘛,只有升序或者是降序的数字里面查找,有这个想法的是大错特错的,在一些题目中有些无序也可以使用二分查找,所以说二分查找的知识点没有我们想的那么简单,在二分查找中我们会总结一些模板,这些模板要死记硬背要理解哦,题目选取的很多,大家不要跳过一些题目,有些题目是为后面的题目做铺垫的,望大家可以从头看到尾,这里就简单的总结一些二分查找的知识点:
- 二分查找的时间复杂度:log(N)
- 二分查找的范围:有序的数组或者无序
⭐经典题型
🌙topic-->1
题目链接:、
题目分析:
在一个有序的数组中查找一个数字 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
题目链接:
题目分析:
在一个非递归中找一个等于 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
这道题目就不再讲解的这么细了,具体还得琢磨第二道题目:
题目链接:
题目分析:
给定一个排序数
给定一个排序数组(升序)和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
算法原理:
- 解法一:
暴力遍历数组,时间复杂度为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
这道题目就不再讲解的这么细了,具体还得琢磨第二道题目:
题目链接:
题目分析:
求 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
这道题目就不再讲解的这么细了,具体还得琢磨第二道题目:
题目链接:
题目分析:
有一个山峰数组(数组有递增和递减),返回数组中峰顶的下标。
算法原理:
- 解法一:
暴力遍历数组就可以了,时间复杂度为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
这道题目就不再讲解的这么细了,这里和第五道题目几乎一样:
题目链接:
题目分析:
有一个山峰数组,这个山峰数组有多个山峰,只要返回其中一峰顶就行(返回数组中峰顶的下标)
算法原理:
- 解法一:
暴力遍历数组就可以了,时间复杂度为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
这道题目就不再讲解的这么细了,具体还得琢磨第二道题目:
题目链接:
题目分析:
在一个数组中找最小值。
算法原理:
- 解法一:
暴力遍历数组就可以了,时间复杂度为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
这道题目就不再讲解的这么细了,具体还得琢磨第二道题目:
题目链接:
题目分析:
在一个 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; } } };
🌟结束语
今天内容就到这里啦,时间过得很快,大家沉下心来好好学习,会有一定的收获的,大家多多坚持,嘻嘻,成功路上注定孤独,因为坚持的人不多。那请大家举起自己的小手给博主一键三连,有你们的支持是我最大的动力💞💞💞,回见。