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

力扣链接

在理解35的基础上再次加强。

其实就是要我们找target的左边界和右边界。35里的逻辑其实就是一个寻找边界的过程，只需要把相等的情况并入其中一个方向，就可以应用到这种非递减数列里面。现在需要寻找2个边界，那就需要2次二分查找。常数加个2,时间复杂度还是log。

找左边界

while (left <= right) {
	middle = (left + right) / 2;
	if (nums[middle] >= target) {
		right = middle - 1; // right及其左都是小于
	}
	else {
		left = middle + 1; // left及其右都是大于等于
	}
}
res[0] = left; 
// 如果target有的话，left这里就是第一个target，没有，left这里就是第一个大于

只要大于等于target，就把right往左边推，所以right及其左都是小于； 只要小于target，就把left往右边推，所以left及其右都是大于等于。 这样第一个大于等于target就是left。

找右边界

while (left <= right) {
	middle = (left + right) / 2;
	if (nums[middle] <= target) {
		left = middle + 1; // left及其右都是大于
	}
	else {
		right = middle - 1; // right及其左都是小于等于
	}
}
res[1] = right; 
// 如果target有的话，right这里就是最后一个target，没有，left这里就是最后一个小于

同理。

处理不存在情况

有target存在，第一个大于等于target的位置，一定小于等于最后一个小于等于target的位置。 但是没有target的情况就不一样了，因为第一个大于于target的位置，一定大于等于最后一个小于target的位置。 于是我们可以以此来判断到底存不存在。只要这个res[0] > res[1]成立，那就知道不存在，两个改成-1就好了。

完整代码

class Solution {
  public:
	vector<int> searchRange(vector<int> &nums, int target)
	{
		vector<int> res(2);
		int left = 0, right = nums.size() - 1, middle;
		while (left <= right) {
			middle = (left + right) / 2;
			if (nums[middle] <= target) {
				left = middle + 1; // left及其右都是大于
			}
			else {
				right = middle - 1; // right及其左都是小于等于
			}
		}
		res[1] =
			right; // 如果target有的话，right这里就是最后一个target，没有，left这里就是最后一个小于
		left = 0, right = nums.size() - 1;
		while (left <= right) {
			middle = (left + right) / 2;
			if (nums[middle] >= target) {
				right = middle - 1; // right及其左都是小于
			}
			else {
				left = middle + 1; // left及其右都是大于等于
			}
		}
		res[0] =
			left; // 如果target有的话，left这里就是第一个target，没有，left这里就是第一个大于
		// 如果target有，那很对，res[0] <= res[1],
		//  如果target没， res[0]是第一个大于target，
		//  res[1]是最后一个小于target,一定是res[0] > res[1]
		if (res[0] > res[1]) {
			res[0] = -1;
			res[1] = -1;
		}
		return res;
	}
};