# 1.在排序数组中查找元素的第一个和最后一个位置（middle）
# 一、题目
LeetCode 34.在排序数组中查找元素的第一个和最后一个位置 (opens new window)
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置，如果数组中不存在目标值 target，返回 [-1, -1]。
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
提示：
- nums 是一个非递减数组
# 二、基础模版 III
因为我们的判断区间最少为2个元素，所以我们要注意循环的执行条件
- 简单的判断边界：
nums.length === 0，return -1； - 定义初始的左右边界：
left = 0, right = nums.length - 1； - 确定执行条件：
left + 1 < right，这也意味着查找区间要存在 3 个元素； - 向左查找时：
right = mid； - 向左查找时：
left = mid； - 判断剩下的两个元素哪个符合目标元素，并返回结果；
# 三、题解
分析模版
- 我们的目标是：寻找目标值的起始下标和终止下标，但它是可能重复的
- 针对这样的情况，我们要将判断拆解成查找目标首次出现的位置，和最后一次出现的位置
var searchRange = function(nums, target) {
const NO_TARGET = [-1, -1];
if (nums.length === 0) return NO_TARGET;
// 判断首次位置
let firstPosition = findFirstPos(nums, target);
if (firstPosition < 0) return NO_TARGET;
// 获取最终出现位置
let lastPostion = findLastPos(nums, target);
return [firstPosition, lastPostion];
};
// 首次出现目标位置，参考模板II
const findFirstPos = function(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
let mid = left + ((right - left) >> 1);
if (nums[mid] === target) {
right = mid; // 舍弃右侧，留mid，不管右侧是否有重复值，我们只留1个满足条件的
} else if (nums[mid] > target) {
right = mid - 1; // 直接舍弃
} else {
left = mid + 1; // 直接舍弃
}
}
if (nums[left] === target) return left;
return -1;
}
// 首次出现目标位置，参考模板II
const findLastPos = function(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
let mid = left + ((right - left + 1) >> 1); // 注意这里 + 1是为了向上取整，因为我们要查找最后出现的元素
if (nums[mid] === target) {
left = mid; // 舍弃右侧，留mid
} else if (nums[mid] > target) {
right = mid - 1; // 直接舍弃
} else {
left = mid + 1;
}
}
if (nums[left] === target) return left;
return -1;
}
# 四、写在最后
本文是二分查找-模版III 的第一题，后面的几道题的也算是本模版的微调版，加油～
如果对你有所帮助不妨给本项目的github 点个 star (opens new window)，这是对我最大的鼓励
关于我
- 花名：余光
- WX：j565017805
- 沉迷 JS，水平有限，虚心学习中
其他沉淀
