对排序的数组查找目标值的左右边界。
ex. [5,7,7,8,8,10] , target 8 => [3,4].
思考：对于已经排序的数组，通常会想到二分插入，这道题使用二分查找的变体即可。分别找到左右边界。
int LeftBound(vector<int> &nums, int target) { int begin = 0; int end = nums.size() - 1; // 要有等于：可能是begin和end都指向同一个target位置，也可能指向非值为target的位置 while(begin <= end) { int mid = (begin + end) / 2; if(target == nums[mid]) { if(mid == 0 || target > nums[mid - 1]) return mid; end = mid - 1; } else if(target > nums[mid]) { begin = mid + 1; } else { end = mid - 1; } } return -1; } int RightBound(vector<int> &nums, int target) { int begin = 0; int end = nums.size() - 1; while(begin <= end) { int mid = (begin + end) / 2; if(target == nums[mid]) { if(mid == nums.size() - 1 || target < nums[mid + 1]) return mid; begin = mid + 1; } else if(target > nums[mid]) { begin = mid + 1; } else { end = mid - 1; } } return -1; } vector<int> searchRange(vector<int>& nums, int target) { vector<int> v; v.push_back(LeftBound(nums, target)); v.push_back(RightBound(nums, target)); return v; }
