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

题目

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

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

进阶

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

示例

输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]

输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]

输入：nums = [], target = 0 输出：[-1,-1]

提示

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

算法

二分查找（O(logn)时间复杂度）

先使用二分查找找到一个符合的位置，然后从这个位置向左向右查找边界

export const searchRange = (nums, target) => {
	let targetIndex = binarySearch(nums, target);
	if (targetIndex >= 0) {
		let l = targetIndex,
			r = targetIndex;
		while (l >= 0 && nums[l] === target) l--;
		while (r < nums.length && nums[r] === target) r++;
		return [l + 1, r - 1];
	}
	return [-1, -1];
};
const binarySearch = (arr, target) => {
	let start = 0,
		end = arr.length - 1;
	while (start <= end) {
		const mid = ~~((start + end) / 2);
		const midEle = arr[mid];
		if (midEle > target) end = mid - 1;
		else if (midEle < target) start = mid + 1;
		else return mid;
	}
	return -1;
};