甘肃城乡建设局安全质量网站,企业平台网站建设方案,广州网站建设维护,深圳网站设计官网一、二分查找算法思想和模版
1.算法思想 2.细节处理 3.模板 二、二分查找
1.链接
704. 二分查找 - 力扣#xff08;LeetCode#xff09;
2.描述 3.思路
先从最经典的题目去切入#xff0c;思路就是二分查找#xff0c;这里我们认为#xff0c;目标值既可以看作为左部…一、二分查找算法思想和模版
1.算法思想 2.细节处理 3.模板 二、二分查找
1.链接
704. 二分查找 - 力扣LeetCode
2.描述 3.思路
先从最经典的题目去切入思路就是二分查找这里我们认为目标值既可以看作为左部分的后端也可以认为是右部分的前端当然有更简单的写法就是直接判断相等但那个方式对二分查找这一类题目的普适性不高作为练习我们这里采用目标值落在左边末端的情况 4.参考代码
认为目标值在左边末端的情况
class Solution {
public:int search(vectorint nums, int target) {int left 0;int 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 left;else return -1;}
}; 三、在排序数组中查找元素的第⼀个和最后⼀个位置
1.链接
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode
2.描述 3.思路
通过分析这题我们需要找到target的开始和末尾我们可以分别进行两次二分查找去分别找到开端和末尾刚好对应着两种不同的策略和模版
target开端我们将数据划分成 【 小于target的数 】【target开端 和大于等于target的数 】 此时目标数据在后半段的开端
target后端数据划分成【小于等于target的数target末尾】【大于target的数】此时目标值在前半段的末端
当然也要考虑不存在target的情况在第一次找开端时若是没找到则可以直接返回{-1-1} 4.参考代码
class Solution {
public:vectorint searchRange(vectorint nums, int target) {//由于有空数组做个特殊处理if(nums.size() 0){return {-1,-1};}//寻找target开端int begin,end;int left 0;int 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) begin left;else return {-1,-1};//寻找target末尾right nums.size()-1;while(left right){int mid left (right - left 1)/2;if(nums[mid] target) left mid;else right mid - 1;}//由于开端已经找到则说明一定存在target末端也一定存在end left;return {begin,end};}
}; 四、搜索插入位置
1.链接
35. 搜索插入位置 - 力扣LeetCode
2.描述 3.思路
根据题意我们不能看出使用二分查找的方法根据题目意思有两种情况
一种是目标值存在那么和最简单的二分查找找目标值那题是一样的采用哪种策略划分都可以
另一种是不存在则返回插入位置的索引这个插入位置的索引原先是比target较大一点的值
因此我们将区域划分为【小于target的值】【大于等于target的值】此时我们要找到目标索引就是后半部分的开端
此外还需要考虑边界情况
1.数组内的数全都大于target
最终right在不断调整下会落在0上是满足题意的
2.数组内的数全都小于target
最终left会落在right最后一个位置的索引但实际要求插入的位置是right1的地方
所以这里做一个判断若是最终出来的值小于target则返回right1left1 4.参考代码
class Solution
{
public:int searchInsert(vectorint nums, int target) {int left 0;int 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) left;return left;}
}; 五、x的平方根
1.链接
69. x 的平方根 - 力扣LeetCode
2.描述 3.思路
根据题意我们可以认为目标值的范围一定会是在【1x】区间我们根据这个区间内每个数的平方去划分前后两个区间【平方小于等于x的数】【平方大于x的数】我们要找的目标值落在前半部分区间的末端
考虑边界情况目标值一定会存在但是x从0开始因此我们需要对x0时的情况做一个特殊处理
4.参考代码
class Solution {
public:int mySqrt(int x) {if(x 0) return 0;int left 1;int 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;}
}; 六、山脉数组的峰值索引
1.链接
852. 山脉数组的峰顶索引 - 力扣LeetCode
2.描述 3.思路
通过题意我们可以将数据划分为这两种情况 【前半部分都是递增的数据】【后半部分全是递减的数据】我们要找到目标值可以认为是在前半部分的末端也可以认为是后半部分的开端任选一个即可
由于题目说一定是山峰数组且数组长度大于等于3因此可以不考虑特殊情况
这题需要稍微分析的就是条件的判断
若是认为目标值在前半段的末端则在判断递增还是递减时则需要前一个比较后一个
若是认为目标值在后半段开端则判断递增还是递减时需要后一个比较前一个 4.参考代码
class Solution {
public:int peakIndexInMountainArray(vectorint arr) {int left 0;int right arr.size()-1;while(leftright){int mid left (right - left 1)/2;if(arr[mid] arr[mid-1]) left mid;else right mid -1;}return left;} 七、寻找峰值
1.链接
162. 寻找峰值 - 力扣LeetCode
2.描述 3.思路
只需要找到数组中任意一个峰值即可因此思路和上一题是一样的 4.参考代码
class Solution {
public:int findPeakElement(vectorint nums) {int left 0;int right nums.size()-1;while(left right){int mid left (right - left 1)/2;if(nums[mid] nums[mid-1]) left mid;else right mid -1;}return left;}
}; 八、搜索旋转排序数组中的最小值
1.链接
153. 寻找旋转排序数组中的最小值 - 力扣LeetCode
2.描述 3.思路 4.参考代码
class Solution {
public:int findMin(vectorint nums) {int left 0;int right nums.size()-1;int x nums[right];while(left right){int mid left (right - left)/2;if(nums[mid] x) left mid1;else right mid;}return nums[left];}
}; 九、点名
1.链接
LCR 173. 点名 - 力扣LeetCode
2.描述 3.思路
根据题意我们知道若是没有人缺席下标和数字应该会严格的一一对应的我们可以将数据划分为前后两段【下标和元素严格对应】【下标和元素没有对应】我们的目标值就落在后半段的开端
还需要考虑一下边界条件若是恰好最后一位同学缺席此时该算法会算到倒数第二位学号的同学此时在返回时做一个判断即可
return left records[left] ? left1:left ; 4.参考代码
class Solution {
public:int takeAttendance(vectorint records) {int left 0;int right records.size()-1;while(left right){int mid left (right - left)/2;if(records[mid] mid) left mid1;else right mid;}return left records[left] ? left1:left;}
}; 总结
本章介绍了二分查找的算法思想并且整理了相关的经典题目从简单到难的去逐步递进并且提供了链接和描述可以直接通过链接去练习或者直接看本篇博客去尝试思考解题还提供了参考的思路部分困难的题目会结合图像去分析还有测试通过的参考代码
