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的值则结束。
分别定义一个用于找左右两侧的递归函数，函数内不断二分。

var searchRange = function(nums, target) {if(nums.length==0)  return [-1,-1]var left = 0var right = nums.length-1var 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)//如果没找到，则左侧的值就是midif(leftIndex==-1)   leftIndex=mid//如果没找到，则右侧的值就是midif(rightIndex==-1)  rightIndex=midreturn [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 -1let 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 midreturn index}else{return findLeft(nums,target,mid+1,right)}
}
function findRight(nums,target,left,right){if(left>right)  return -1let mid = Math.floor((left+right)/2)if(nums[mid]==target){let index = findRight(nums,target,mid+1,right)if(index==-1)   return midreturn index}else{return findRight(nums,target,left,mid-1)}
}