34. 在排序数组中查找元素的第一个和最后一个位置-Toy模板网

这篇具有很好参考价值的文章主要介绍了34. 在排序数组中查找元素的第一个和最后一个位置。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

难度：中等
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 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的中间值，再分别在这个中间值的左右两侧内继续二分，直到找到最后一个等于target的值则结束。
分别定义一个用于找左右两侧的递归函数，函数内不断二分。文章来源地址https://www.toymoban.com/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){//找到这个值，则开始在这个值的左右两侧找
            let leftIndex = findLeft(nums,target,left,mid-1)
            let rightIndex = findRight(nums,target,mid+1,right)
            //如果没找到，则左侧的值就是mid
            if(leftIndex==-1)   leftIndex=mid
            //如果没找到，则右侧的值就是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){
	//递归的结束条件
    if(left>right)  return -1
    let mid = Math.floor((left+right)/2)
    if(nums[mid]==target){
        let index = findLeft(nums,target,left,mid-1)
        //最后一层的递归结束，left-right=1，返回index=-1，则倒数第二层，left=right=mid,返回mid,此时mid就是要求的左侧的值
        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)
    }
}