34. Find First and Last Position of Element in Sorted Array 二分搜索

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

29

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;}
};