| 
 | 
 
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册  
 
x
 
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 
 
如果数组中不存在目标值 target,返回 [-1, -1]。 
 
进阶: 
 
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗? 
  
 
示例 1: 
 
输入:nums = [5,7,7,8,8,10], target = 8 
输出:[3,4] 
示例 2: 
 
输入:nums = [5,7,7,8,8,10], target = 6 
输出:[-1,-1] 
示例 3: 
 
输入:nums = [], target = 0 
输出:[-1,-1] 
  
 
提示: 
 
0 <= nums.length <= 105 
-109 <= nums[i] <= 109 
nums 是一个非递减数组 
-109 <= target <= 109 
 
来源:力扣(LeetCode) 
链接:https://leetcode-cn.com/problems ... ent-in-sorted-array 
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 
目前的思路是: 
左右分别用二分法找到边界然后输出,在力扣上示例通过,源代码在文章后面,目前遇到的问题是: 
输入: 
[5,7,7,8,8,10] 
6 
输出: 
[-1,0] 
预期结果: 
[-1,-1] 
源代码: 
class Solution { 
public: 
    vector<int> searchRange(vector<int>& nums, int target) { 
         vector <int> answer= {LeftBound(nums,target),RightBound(nums,target)}; 
         return answer; 
    } 
 
        int LeftBound (vector<int>nums,int target) 
        { 
            int left = 0; 
        int right = nums.size(); 
        while(right>left) 
        { 
            int mid =(left+right)/2; 
            if(nums[mid]>=target) 
            { 
                right=mid; 
            } 
            else 
            { 
                left=mid+1; 
            } 
        } 
          if(left==nums.size()||nums[left]!=target) 
            { 
                return -1; 
            } 
          return left; 
        }   
        int RightBound (vector<int>nums,int target) 
        { 
        int left1=0; 
        int right1=nums.size();//搜索区间为[left1,right1) 
        while(left1<right1)//查找有边界 
        { 
            int mid =(left1+right1)/2; 
            if(nums[mid]<=target) 
            { 
                left1=mid+1; 
            } 
            else  
            { 
                right1=mid; 
            } 
        } 
         if(left1==nums.size()||right1==0) 
            { 
                return -1; 
            } 
        return left1-1; 
        } 
}; |   
 
 
 
 |