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

题意：

一个有序数组中有重复元素，返回第一个和最后一个target的下标。要求O（logN）。

思路：

没什么好说的，还是二分法。

vector<int> searchRange(vector<int>& nums, int target) {
	int l = 0, r = nums.size() - 1, mid, sz = nums.size(), get = -1;
	if (sz == 0)
		return{ -1,-1 };
	while (l <= r) {
		mid = (l + r) / 2;
		if (nums[mid] == target) {
			get = mid;
			break;
		}
		else if (nums[mid] > target)
			r = mid - 1;
		else
			l = mid + 1;
	}
	if (get == -1)
		return{ -1,-1 };
	int first = get, last = get;
	while (first >= 1 && nums[first - 1] == nums[first])
		--first;
	while (last <= sz - 2 && nums[last + 1] == nums[last])
		++last;
	return{ first,last };
}