Leetcode刷题(第34题)——在排序数组中查找元素的第一个和最后一个位置

x33g5p2x  于2022-02-28 转载在 其他  
字(0.6k)|赞(0)|评价(0)|浏览(277)

一、题目

二、示例

示例一
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

示例二:
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]

示例三:
输入:nums = [], target = 0
输出:[-1,-1]

三、思路
时间复杂度为O(logn),肯定是二分查找,只不过需要在找到值后,然后再在该下标周围查找是否存在和target相等的值。
四、代码解题

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    let left = 0
    let length = nums.length
    let right = length - 1
    let ret = -1
    while(left <= right) {
        let mid = Math.floor((left + right) / 2)
        if(target === nums[mid]) {
            ret = mid
            let l = ret - 1
            let r = ret + 1
            while(l >= 0 && nums[l] === target) {
                l--
            }
            while(r < length && nums[r] === target) {
                r++
            }
            return [l+1, r-1]
        }else if(target > nums[mid]) {
            left = mid + 1
        }else {
            right = mid - 1
        }
    }
    return [-1, -1]
};

五、结果

相关文章