34. Find First and Last Position of Element in Sorted Array

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

本题给了一个有重复元素的升序排序数组 nums 以及一个 target

题目要求我们找出数组中 target 的下标范围

解题思路

题目要求我们用 logn 的复杂度来解，所以我们还是需要用到二分法来计算

问题是，一般的二分搜索只能够用来确定单个元素的位置，无法确定范围

所以我们需要进行一些改动，我们需要解决两个问题：如何确定范围、如何找到边界

确定范围的部份我们需要用到两次二分搜索来确定题目要求的左下标与右下标

寻找边界的部份我们可以用一个变量来保存最后一次找到元素的位置

Javascript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
    let left = 0
    let right = nums.length - 1
    const leftBoundary = searchLeftBoundry(nums, target, left, right)
    const rightBoundary = searchRightBoundary(nums, target, left, right)

    return [leftBoundary, rightBoundary]
};

const searchLeftBoundry = (nums, target, left, right) => {
    let res = -1
    while (left <= right) {
        let mid = (left + right) >> 1

        if(nums[mid] === target) {
            res = mid
        }

        if(nums[mid] >= target) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return res
}

const searchRightBoundary = (nums, target, left, right) => {
    let res = -1
    while (left <= right) {
        let mid = (left + right) >> 1

        if(nums[mid] === target) {
            res = mid
        }

        if(nums[mid] <= target) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return res
}