在排序数组中查找元素的第一个和最后一个位置

题目描述：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

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

进阶：

• 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例说明请见LeetCode官网。

来源：力扣（LeetCode）   

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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：二分查找、递归

用left和right记录开始位置和结束位置，用二分查找法查找target在nums中的位置，从0到nums.length-1分别记为low和high，mid表示中间值，具体过程如下：

• 计算mid为low和high的中间值；

• 如果mid的值和target相等，则判断mid左边的元素是否跟target相等，如果相等，则递归查找开始位置，从low到mid-1查找，如果不相等，则left为mid；判断mid右边的元素是否跟target相等，如果相等，则递归查找结束位置，从mid+1到high查找，如果不相等，则right为mid；

• 如果mid的值大于target，则high更新为mid-1；

• 如果mid的值小于target，则low更新为mid+1。

查找完成后返回left和right即为最终结果。

【每日寄语】 阳春三月，万物复苏，愿所有美好如期而至。