做一款网站注意啥,百度网址输入,泰安房产网租房,重庆森林百度网盘创作不易#xff0c;感谢三连#xff01;#xff01;
一、二分查找算法思路总结
大家先看总结#xff0c;然后再根据后面的题型去慢慢领悟 二、二分查找#xff08;easy#xff09;
. - 力扣#xff08;LeetCode#xff09;二分查找 思路#xff1a;#xff08;模… 创作不易感谢三连
一、二分查找算法思路总结
大家先看总结然后再根据后面的题型去慢慢领悟 二、二分查找easy
. - 力扣LeetCode二分查找 思路模版1正常的二分查找策略
class Solution {
public:int search(vectorint nums, int target){int left0,rightnums.size()-1;while(leftright){int midleft(right-left)/2;if(nums[mid]target) leftmid1;else if(nums[mid]target) rightmid-1;else return mid;}return -1;}
};
三、在排序数组中查找元素的第一个位置和最后一个位置
. - 力扣LeetCode在排序数组中查找元素的第一个位置和最后一个位置 要注意示例3提到的边界情况
思路找第一个用左区间端点查找模版2找最后一个用右端点区间查找模版3
class Solution {
public:vectorint searchRange(vectorint nums, int target){if(nums.size()0) return {-1,-1};//处理边界情况否则会越界int begin0;//区间左端点int left0,rightnums.size()-1;while(leftright){int midleft(right-left)/2;if(nums[mid]target) leftmid1;else rightmid;//最后会落在区间的左端点}if(nums[left]!target) return{-1,-1};//找不到else beginleft;//区间右端点rightnums.size()-1;while(leftright){int midleft(right-left1)/2;if(nums[mid]target) leftmid;//最后会落在区间的右端点else rightmid-1;}return {begin,right};//此时至少有一个左端点所以不可能找不到。}
};
四、x的平方根 . - 力扣LeetCodex的平方根
思路右端区间二分查找法 class Solution {
public:int mySqrt(int x) {if(x1) return 0;//处理边界情况int left1,rightx/2;while(leftright){long long midleft(right-left1)/2;if(mid*midx) rightmid-1;else leftmid;}return left;}
}; 五、搜索插入位置
. - 力扣LeetCode搜索插入位置 思路1左端区间查找
class Solution {
public:int searchInsert(vectorint nums, int target) {int left0,rightnums.size()-1;while(leftright){int midleft(right-left)/2;if(nums[mid]target) leftmid1;else rightmid;}if(nums[left]target) return left1;return left;}
};
思路2右端区间查找有特殊情况比如正好是和targe相等且只有一个元素
class Solution {
public:int searchInsert(vectorint nums, int target) {int left0,rightnums.size()-1;while(leftright){int midleft(right-left1)/2;if(nums[mid]target) leftmid;else rightmid-1;}//右端区间要考虑边界情况特殊情况只有一个元素且正好等于targetif(nums[left]target) return left;return left1;}
}; 六、山峰数组峰顶的索引 . - 力扣LeetCode山峰数组峰顶的索引
本题特别的就是不再是升序而是去找二段性的规律 思路1左端区间查找
class Solution {
public:int peakIndexInMountainArray(vectorint arr){int left1,rightarr.size()-2;while(leftright){int midleft(right-left)/2;if(arr[mid]arr[mid1]) leftmid1;else rightmid; }return left;}
};
思路2右端区间查找
class Solution {
public:int peakIndexInMountainArray(vectorint arr){int left1,rightarr.size()-2;while(leftright){int midleft(right-left1)/2;if(arr[mid]arr[mid-1]) leftmid;else rightmid-1; }return left;}
};
七、寻找峰值
. - 力扣LeetCode寻找峰值 左区间端点法
class Solution {
public:int findPeakElement(vectorint nums) {int left0,rightnums.size()-1;while(leftright){int midleft(right-left)/2;if(nums[mid]nums[mid1]) leftmid1;else rightmid;}return right;}
};
右区间端点法
class Solution {
public:int findPeakElement(vectorint nums) {int left0,rightnums.size()-1;while(leftright){int midleft(right-left1)/2;if(nums[mid]nums[mid-1]) leftmid;else rightmid-1;}return right;}
}; 八、点名
. - 力扣LeetCode点名 左区间端点法
class Solution {
public:int takeAttendance(vectorint records) {int left0,rightrecords.size()-1;while(leftright){int midleft(right-left)/2;if(records[mid]mid) leftmid1;else rightmid;}if(records[right]right) return right1;else return right;}
};
注意插入元素的时候要注意是否是在最右边插入
九、 寻找旋转数组中的最小值
. - 力扣LeetCode寻找旋转数组中的最小值 思路左区间端点查找法
class Solution {
public:int findMin(vectorint nums) {int left0,rightnums.size()-1;int targetnums[right];//标记一下while(leftright){int midleft(right-left)/2;if(nums[mid]target) leftmid1;else rightmid;}return nums[left];}
};
十、二分查找规律的再总结 二分查找的策略基本上都是去找一个数对应的有三种模版正常的二分查找、左区间端点查找、右区间端点查找。其中正常的二分查找局限性比较大必须得是升序且限制条件较多大多数情况下不符合题意。最常用的就是左区间端点关键是left会大跳跃且目标位置在较大值区间的左边和右区间端点法关键是right会大跳跃且目标位置在较小值区间的右边。 后面有遇到相关oj题博主会继续更新的……感谢支持
