博客

leetcode34题。在排序数组中查找元素的第一个和最后一个位置

其中的mid=left+(right-left)/2;是一个比较常规的优化，可以防止左右边界加和出现int数据的溢出问题。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int begin=0,end=nums.size()-1,mid;
        //条件不满足就直接进行返回，如不熟悉不建议使用goto语句
		if(nums.size()==0||target<nums[0]||target>*(nums.end()-1))
			goto L1;
		while (begin<=end)
		{
			mid = begin + (end - begin) / 2;//防止溢出
			if(nums[mid]==target){
				break;
			}else if(nums[mid]>target){
				end=mid-1;
			}else{
				begin=mid+1;
			}
		}
		if(nums[mid]==target){
			//获取左边界
			int left=0,right=mid,end=mid;//end临时保存mid数值
			while(left<right){
				//与下面的不同点在于，没有修正mid的位置，因为此时我们的mid总是我们的右边界左边的数值
				mid=left+(right-left)/2;
				if(nums[mid]==target){//右边界永远等于target
					right=mid;
				}else if(nums[mid]<target){
					left=mid+1;
				}
			}
			begin=right;
			left=end;
			right=nums.size()-1;
			while (left<right)
			{
				//之所以是mid+1，是因为我们总是要判断左边界右边的数值，才能够收缩边界
				mid=left+(right-left)/2+1;
				if(nums[mid]==target){//左边界永远等于target
					left=mid;
				}else if(nums[mid]>target){
					right=mid-1;
				}
			}
			end=left;
			return vector<int>({begin,end});
		}
		L1:
		return vector<int>({-1,-1});	
    }
};