34. Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

---

给定一个有序数组，里面可能有重复元素，要求找出某个元素所有出现位置的起始位置和终止位置。

由于是有序数组，所以直接二分搜索，需要注意的是如果是找起始位置，则找到目标元素后还应该继续往左找，可以想象mid一直遇到target，则要不断执行r=mid-1，直到退出while循环，此时老的mid是等于target的最小下标，所以要返回r+1。类似的，如果找终止位置，则遇到相等后还要继续往右找，即l=mid+1，失败的时候返回上一个mid，即l-1。

完整代码如下：

class Solution {
public:
	int FindFirstIndex(vector<int>& nums, int target) {
		int l = 0, r = nums.size() - 1;
		while (l <= r) {
			int mid = l + (r - l) / 2;
			if (target <= nums[mid])r = mid - 1;
			else l = mid + 1;
		}
		if (r + 1 < nums.size() && nums[r + 1] == target)return r + 1;
		else return -1;
	}
	int FindLastIndex(vector<int>& nums, int target) {
		int l = 0, r = nums.size() - 1;
		while (l <= r) {
			int mid = l + (r - l) / 2;
			if (target >= nums[mid])l = mid + 1;
			else r = mid - 1;
		}
		if (l - 1 >= 0 && nums[l - 1] == target)return l - 1;
		else return -1;
	}
	vector<int> searchRange(vector<int>& nums, int target) {
		return { FindFirstIndex(nums,target),FindLastIndex(nums,target) };
	}
};

本代码提交AC，用时4MS。