零 题目：算法（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;
};