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]

提示：

0 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
nums 是一个非递减数组
-10⁹ <= target <= 10⁹

分析：

面对这道算法题目，二当家的陷入了沉思。
有序数组中查找元素，而且要求时间复杂度为 O(log n) ，那肯定要用二分查找法了，但是题目要找两个位置，所以我们需要两次二分查找，可是结果要一头一尾，逻辑不一样，难道写两个二分吗？其实可以复用，我们实现一个查找指定元素的第一个位置，但是多一个参数来传递是否包含相等元素，所以结果中查找元素的第一个位置，就是二分查找大于等于指定元素的第一个位置，结果中查找元素的最后一个位置，就是二分查找大于指定元素的第一个位置再减一。

题解：

rust

impl Solution {pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {fn binary_search(nums: &Vec<i32>, target: i32, include_eq: bool) -> usize {if nums.is_empty() {return 0;}let (mut left, mut right, mut ans) = (0, nums.len() - 1, nums.len());while left <= right {let mid = (left + right) >> 1;if nums[mid] > target || (include_eq && nums[mid] == target) {ans = mid;if mid == 0 {break;}right = mid - 1;} else {left = mid + 1;}}return ans;}let left_idx = binary_search(&nums, target, true);let right_idx = binary_search(&nums, target, false) - 1;if left_idx <= right_idx && right_idx < nums.len() && nums[left_idx] == target && nums[right_idx] == target {return vec![left_idx as i32, right_idx as i32];}return vec![-1, -1];}
}

go

func searchRange(nums []int, target int) []int {leftIdx := sort.SearchInts(nums, target)if leftIdx == len(nums) || nums[leftIdx] != target {return []int{-1, -1}}rightIdx := sort.SearchInts(nums, target+1) - 1return []int{leftIdx, rightIdx}
}

c++

class Solution {
public:vector<int> searchRange(vector<int> &nums, int target) {int leftIdx = lower_bound(nums.begin(), nums.end(), target) - nums.begin();int rightIdx = lower_bound(nums.begin(), nums.end(), target + 1) - nums.begin() - 1;if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {return vector<int>{leftIdx, rightIdx};}return vector<int>{-1, -1};}
};

c

int binarySearch(int* nums, int numsSize, int target, bool includeEq) {int left = 0, right = numsSize - 1, ans = numsSize;while (left <= right) {int mid = (left + right) >> 1;if (nums[mid] > target || (includeEq && nums[mid] == target)) {right = mid - 1;ans = mid;} else {left = mid + 1;}}return ans;
}/*** Note: The returned array must be malloced, assume caller calls free().*/
int* searchRange(int* nums, int numsSize, int target, int* returnSize){int leftIdx = binarySearch(nums, numsSize, target, true);int rightIdx = binarySearch(nums, numsSize, target, false) - 1;int *ans = malloc(sizeof(int) * 2);*returnSize = 2;if (leftIdx <= rightIdx && rightIdx < numsSize && nums[leftIdx] == target && nums[rightIdx] == target) {ans[0] = leftIdx, ans[1] = rightIdx;} else {ans[0] = -1, ans[1] = -1;}return ans;
}

python

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:def binary_search(include_eq: bool):left, right, ans = 0, len(nums) - 1, len(nums)while left <= right:mid = (left + right) >> 1if nums[mid] > target or (include_eq and nums[mid] == target):right = mid - 1ans = midelse:left = mid + 1return ansleft_idx = binary_search(True)right_idx = binary_search(False) - 1if left_idx <= right_idx < len(nums) and nums[left_idx] == target and nums[right_idx] == target:return [left_idx, right_idx]return [-1, -1]

java

class Solution {public int[] searchRange(int[] nums, int target) {int leftIdx = binarySearch(nums, target, true);int rightIdx = binarySearch(nums, target, false) - 1;if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {return new int[]{leftIdx, rightIdx};} return new int[]{-1, -1};}private int binarySearch(int[] nums, int target, boolean includeEq) {int left = 0, right = nums.length - 1, ans = nums.length;while (left <= right) {int mid = (left + right) >> 1;if (nums[mid] > target || (includeEq && nums[mid] == target)) {right = mid - 1;ans = mid;} else {left = mid + 1;}}return ans;}
}