二分查找算法(2) _在排序数组中查找元素的第一个和最后一个_模板
个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创二分查找算法(2) _在排序数组中查找元素的第一个和最后一个_模板
收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌
目录
1. 题目链接:
OJ链接: 在排序数组中查找元素的第一个和最后一个
2. 题目描述 :
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10] , target = 8 输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10] , target = 6 输出：[-1,-1]
示例 3：
输入：nums = [], target = 0 输出：[-1,-1]
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109nums是一个非递减数组-109 <= target <= 109
3. 解法 :
解法一:暴力枚举遍历:
算法思路 :
使用两个头尾指针遍历整个数组,在排序数组中查找元素的第一个和最后一个
代码展示 :
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while(left < right)
{
if(nums[left] < target) left++;
else if(nums[right] > target) right--;
else break;
}
if(left <= right && nums[left] == target && nums[right] == target)
return {left, right};
else return{-1, -1};
}
};
结果分析 :
题目顺利通过!时间复杂度为: O(N),不过算法还有进一步优化的空间.
解法二: 二分查找 :
算法思路 :
a.分析插⼊位置左右两侧区间上元素的特点：
设插⼊位置的坐标为 index ，根据插⼊位置的特点可以知道：
•[left, index - 1] 内的所有元素均是⼩于 target 的；
•[index, right] 内的所有元素均是⼤于等于 target 的。
b.设 left 为本轮查询的左边界， right 为本轮查询的右边界。根据 mid 位置元素的信
息，分析下⼀轮查询的区间：
▪ 当 nums[mid] >= target 时，说明 mid 落在了[index, right] 区间上，
mid 左边包括 mid 本⾝，可能是最终结果，所以我们接下来查找的区间在[left,
mid] 上。因此，更新 right 到 mid 位置，继续查找。
▪ 当 nums[mid] < target 时，说明 mid 落在了[left, index - 1] 区间上，
mid 右边但不包括 mid 本⾝，可能是最终结果，所以我们接下来查找的区间在[mid
+ 1, right] 上。因此，更新 left 到 mid + 1 的位置，继续查找。c.直到我们的查找区间的⻓度变为 1 ，也就是 left == right 的时候， left 或者
right 所在的位置就是我们要找的结果。
总结:
查找区间左端点 --- [..., target) [target, ...]
1. nums[mid] < t left = mid + 1
2. nums[mid] >= t right = mid
查找区间右端点 --- [..., target] (target, ...]
1. nums[mid] <= t left = mid
2. nums[mid] > t right = mid - 1
细节处理:
查找区间的左端点
1. 循环条件
while(left < right)
注意这里不能使用while(left <= right)
1. 有结果: 当我们的left == right时,我们的left即是我们的结果,但如果你是使用while(left <= right) 循环,程序会陷入死循环,因为此时right + left / 2 = right/left
2. 全部大于target: 那我们的right会一直往左走,直到left与right相遇,这时候我们只需要判断它们相遇点的值是否等于target就行,相反使用while(left <= right)循环,程序依旧陷入死循环
3. 全部小于target: 那我们的left会一直往右走,与情况2是一样的
2. 求终点的操作
left + (right - left) / 2
注意这里不能使用left + (right - left + 1) / 2
当我们判断只剩下两个元素时,left指向第一个元素, right指向第二个元素
1. mid = left + (right - left) / 2 = left
2. mid = left + (right - left + 1) / 2 = right
当nums[mid] < target
1: left = mid + 1 =right 循环成功结束
2: left = mid + 1 = right + 1成功错过
当nums[mid] >= target
1: right = mid right == left 循环成功结束
2: right = mid 死循环
查找区间的右端点
1. 循环条件
while(left < right)
原理和查找区间的左端点的一样
2. 求终点的操作
left + (right - left + 1) / 2
注意这里不能使用left + (right - left) / 2
当我们判断只剩下两个元素时,left指向第一个元素, right指向第二个元素
1. mid = left + (right - left) / 2 = left
2. mid = left + (right - left + 1) / 2 = right
当nums[mid] <= target
1: left = mid 死循环
2: left = mid left== right + 1 循环成功结束
当nums[mid] > target
1: right = mid - 1 right == left - 1循环成功错过
2: right = mid - 1 right == left 循环成功结束
代码展示 :
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size() == 0) return {-1, -1};
//找左端点 --- [..., target) [target, ...]
int left = 0, right = nums.size() - 1, begin = 0;
while(left < right)
{
int mid = left + (right - left) / 2;
if(nums[mid] >= target) right = mid;
else left = mid + 1;
}
if(nums[left] == target) begin = left;
else return {-1, -1};
//找右端点 --- [..., target] (target, ...]
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};
}
}; 
结果分析 :
这里一定要注意细节问题,不然程序很容易死循环
4. 二分算法模板总结
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,否侧不加
原文地址：https://blog.csdn.net/wer24_25/article/details/142442272
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！