每天写两道（数组篇）在排序数组中查找元素的第一个和最后一个位置、x的平方根
34.在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组
nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值
target，返回[-1, -1]。你必须设计并实现时间复杂度为
O(log n)的算法解决此问题。
思路：使用二分法分开寻找左右边界值，同时寻找左右边界容易混淆且不好理解
实现：
1.寻找左边边界：
const findLeftBorder = (nums, target)=>{let left = 0let right = nums.length-1let leftBorder = -1while(left <= right){let mid = left+right>>1if(nums[mid] >= target){right = mid - 1leftBorder = right + 1 // 当nums[mid] >= target时修改边界值}else{left = mid + 1}}return leftBorder
}2.寻找右边边界（同理
const findRightBorder = (nums, target)=>{let left = 0let right = nums.length-1let rightBorder = -1while(left <= right){let mid = left+right>>1if(nums[mid] <= target){left = mid + 1rightBorder = left - 1 }else{right = mid - 1}}return rightBorder
}3.如果左右边界都为-1，说明target不在数组区间内；
如果左边界>右边界，说明该数组区间内没有target；
剩下情况直接返回 [leftBorder, rightBorder]
var searchRange = function(nums, target) {const leftBorder = findLeftBorder(nums, target)const rightBorder = findRightBorder(nums, target)if(leftBorder == -1 || rightBorder == -1) return [-1,-1]if(leftBorder > rightBorder) return [-1,-1]return [leftBorder,rightBorder]};69.x的平方根
给你一个非负整数
x，计算并返回x的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如
pow(x, 0.5)或者x ** 0.5。
思路：二分法直接干
实现：
var mySqrt = function(x) {let left = 0let right = xwhile(left <= right){let mid = left + right>>1if(mid*mid == x){return mid}else if(mid*mid < x){left = mid+1}else{right = mid -1}}return right
};