難度：中等
給你一個按照非遞減順序排列的整數(shù)數(shù)組 nums，和一個目標值 target。請你找出給定目標值在數(shù)組中的開始位置和結(jié)束位置。

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

你必須設計并實現(xiàn)時間復雜度為 O(log n) 的算法解決此問題。

示例 1：
輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]

示例 2：
輸入：nums = [5,7,7,8,8,10], target = 6
輸出：[-1,-1]

示例 3：
輸入：nums = [], target = 0
輸出：[-1,-1]

題目要求時間復雜度為O(logn)，就是要我們使用二分法。
思路：
首先不斷二分找到一個nums[mid]==target的中間值，再分別在這個中間值的左右兩側(cè)內(nèi)繼續(xù)二分，直到找到最后一個等于target的值則結(jié)束。
分別定義一個用于找左右兩側(cè)的遞歸函數(shù)，函數(shù)內(nèi)不斷二分。文章來源地址http://www.zghlxwxcb.cn/news/detail-413614.html

var searchRange = function(nums, target) {
    if(nums.length==0)  return [-1,-1]
    var left = 0
    var right = nums.length-1
    var arr = [-1,-1]
    while(left<=right){
        let mid = Math.floor((left+right)/2)
        if(nums[mid]==target){//找到這個值，則開始在這個值的左右兩側(cè)找
            let leftIndex = findLeft(nums,target,left,mid-1)
            let rightIndex = findRight(nums,target,mid+1,right)
            //如果沒找到，則左側(cè)的值就是mid
            if(leftIndex==-1)   leftIndex=mid
            //如果沒找到，則右側(cè)的值就是mid
            if(rightIndex==-1)  rightIndex=mid
            return [leftIndex,rightIndex]
        }else if(nums[mid]<target){
            left = mid + 1
        }else{
            right = mid -1
        }
    }
    return [-1,-1]
};
function findLeft(nums,target,left,right){
	//遞歸的結(jié)束條件
    if(left>right)  return -1
    let mid = Math.floor((left+right)/2)
    if(nums[mid]==target){
        let index = findLeft(nums,target,left,mid-1)
        //最后一層的遞歸結(jié)束，left-right=1，返回index=-1，則倒數(shù)第二層，left=right=mid,返回mid,此時mid就是要求的左側(cè)的值
        if(index==-1)   return mid
        return index
    }else{
        return findLeft(nums,target,mid+1,right)
    }
}
function findRight(nums,target,left,right){
    if(left>right)  return -1
    let mid = Math.floor((left+right)/2)
    if(nums[mid]==target){
        let index = findRight(nums,target,mid+1,right)
        if(index==-1)   return mid
        return index
    }else{
        return findRight(nums,target,left,mid-1)
    }
}

到了這里，關于34. 在排序數(shù)組中查找元素的第一個和最后一個位置的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！