零 标题：算法（leetode，附思维导图 + 全部解法）300题之（34）在排序数组中查找元素的第一个和最后一个位置
一 题目描述
二 解法总览（思维导图）
三 全部解法
1 方案1
1)代码：
// 方案1 “无视要求，直接调用 indexOf、 lastIndexOf”
var searchRange = function(nums, target) {
return [nums.indexOf(target), nums.lastIndexOf(target)];
};
2 方案2
1)代码：
// 方案2 “普通版的双指针”。
// 思路：
// 1）状态初始化
// 2.1）通过移动left，找到 left 的值
// 2.2）通过移动right，找到 right 的值
// 3）根据目前的 left、right 值返回不同的结果
var searchRange = function(nums, target) {
// 1）状态初始化
const l = nums.length;
let left = 0,
right = l - 1;
// 2.1）通过移动left，找到 left 的值
while (left < l) {
if (nums[left] === target) {
break;
}
else if (nums[left] > target) {
left = -1;
break;
}
else {
left++;
}
}
// 2.2）通过移动right，找到 right 的值
while (right >= 0) {
if (nums[right] === target) {
break;
}
else if (nums[right] < target) {
right = -1;
break;
}
else {
right--;
}
}
// 3）根据目前的 left、right 值返回不同的结果。
// 其实下面 4行 等同于
// return left === l ? [-1, -1] : [left, right];
if ([-1, l].includes(left) || [-1, -1].includes(left)) {
return [-1, -1];
}
return [left, right];
}
3 方案3
1)代码：
// 方案3 “二分查找”
// 参考：
// 1）https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-3-4/
const binarySearch = (nums, target, lower) => {
let left = 0, right = nums.length - 1, ans = nums.length;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] > target || (lower && nums[mid] >= target)) {
right = mid - 1;
ans = mid;
} else {
left = mid + 1;
}
}
return ans;
}
var searchRange = function(nums, target) {
const leftIdx = binarySearch(nums, target, true);
const rightIdx = binarySearch(nums, target, false) - 1;
let ans = [-1, -1];
if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] === target && nums[rightIdx] === target) {
ans = [leftIdx, rightIdx];
}
return ans;
};
