在排序数组中查找元素的第一个位置和最后一个位置 - 中等 - 算法题 - 算法 - 计算机

给定一个按照升序排列的整数数组 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 (n)
	*/
	public int[] searchRange(int[] nums, int target) {
	int length = nums.length;
	// 左指针
	int left = 0;
	// 右指针
	int right = length - 1;
	int[] result = new int[]{-1, -1};
	while (left <= right){
	// 当找到结果时返回
	if (result[0] != -1 && result[1] != -1) break;

	// 当未找到第一值时，接着走
	if (result[0] == -1){
	// 找到第一个值
	if (nums[left] == target) result[0] = left;
	// 否则指针右移
	else left++;
	}
	// 当未找到倒数第一个值时，接着走
	if (result[1] == -1){
	// 找到倒数第一个值
	if (nums[right] == target) result[1] = right;
	// 否则指针左移
	else right--;
	}
	}
	return result;
	}

解法二

	public int[] searchRange(int[] nums, int target) {
	// 查找大于目标值 - 1 的下标，就是第一个值的位置
	int left = binarySearch(nums, target - 1);
	// 查找大于目标值的下标 - 1，就是倒数第一个值的位置
	int right = binarySearch(nums, target) - 1;
	if (left <= right && nums[left] == target){
	return new int[]{left, right};
	}
	return new int[]{-1, -1};
	}

	private int binarySearch(int[] nums, int target){
	int length = nums.length;
	int left = 0;
	int right = length - 1;
	int result = length;
	while (left <= right){
	int mid = (left + right) / 2;
	if (nums[mid] > target){
	result = mid;
	right = mid - 1;
	}else {
	left = mid + 1;
	}
	}
	return result;
	}

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array