[[432713]]

給定一個(gè)按照升序排列的整數(shù)數(shù)組 nums ，和一個(gè)目標(biāo)值 target 。找出給定目標(biāo)值在數(shù)組中的開(kāi)始位置和結(jié)束位置。

你的算法時(shí)間復(fù)雜度必須是 O(logn)級(jí)別。

如果數(shù)組中不存在目標(biāo)值，返回 [-1, -1] 。

示例 1:

輸入: nums = [5,7,7,8,8,10], target = 8 
輸出: [3,4] 

示例 2:

輸入: nums = [5,7,7,8,8,10], target = 6 
輸出: [-1,-1] 

解答一：findIndex、lastIndexOf

findIndex() 方法返回?cái)?shù)組中滿足提供的測(cè)試函數(shù)的第一個(gè)元素的索引。若沒(méi)有找到對(duì)應(yīng)元素則返回-1。

lastIndexOf() 方法返回指定元素(也即有效的 JavaScript 值或變量)在數(shù)組中的最后一個(gè)的索引，如果不存在則返回 -1。

解答二：二分查找

let searchRange = function(nums, target) { 
    return [leftSearch(nums, target), rightSearch(nums, target)] 
} 
 
let leftSearch = function(nums, target) { 
    let low = 0,  
        high = nums.length - 1, 
        mid 
    while (low <= high) { 
        mid = Math.floor((low+high)/2) 
        if (nums[mid] < target) { 
            low = mid + 1 
        } else if (nums[mid] > target) { 
            high = mid - 1 
        } else if (nums[mid] === target) { 
            // 這里不返回，繼續(xù)收縮左側(cè)邊界 
            high = mid - 1 
        } 
    } 
    // 最后檢查 low 是否越界或命中 
    if (low >= nums.length || nums[low] != target) 
        return -1 
    return low 
} 
 
 
let rightSearch = function (nums, target) { 
    let low = 0,  
        high = nums.length - 1, 
        mid 
    while (low <= high) { 
        mid = Math.floor((low+high)/2) 
        if (nums[mid] < target) { 
            low = mid + 1 
        } else if (nums[mid] > target) { 
            high = mid - 1 
        } else if (nums[mid] === target) { 
            // 這里不返回，繼續(xù)收縮右側(cè)邊界 
            low = mid + 1 
        } 
    } 
    // 最后檢查 high 是否越界或命中 
    if (high < 0 || nums[high] != target) 
        return -1 
    return high 
} 

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(logn)
• 空間復(fù)雜度：O(1)

leetcode：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/