34. Find First and Last Position of Element in Sorted Array
关于二分搜索的精华帖
按照其方法,分别编写求上下界的二分搜索函数,求得上下界,代码如下:
class Solution {
private:int left_bound(vector& nums, int target){if(nums.size() == 0){return -1;}int left = 0, right = nums.size();while(left < right){int mid = (left + right) / 2;if(nums[mid] == target){right = mid;}else if(nums[mid] < target){left = mid + 1;}else if(nums[mid] > target){right = mid;}}if(left == nums.size()){return -1;}return nums[left] == target ? left : -1;}int right_bound(vector& nums, int target){if(nums.size() == 0){return -1;}int left = 0, right = nums.size();while(left < right){int mid = (left + right) / 2;if(nums[mid] == target){left = mid + 1;}else if(nums[mid] < target){left = mid + 1;}else if(nums[mid] > target){right = mid;}}if(right == 0){return -1;}return nums[right-1] == target ? (right-1) : -1;}
public:vector searchRange(vector& nums, int target) {vector res;int left_b = left_bound(nums, target);if(left_b == -1){res.push_back(-1);res.push_back(-1);return res;}res.push_back(left_b);int right_b = right_bound(nums, target);res.push_back(right_b);return res;}
};










