鱼C论坛

 找回密码
 立即注册
查看: 1063|回复: 0

leecode刷题34题二分法出了点问题

[复制链接]
发表于 2021-12-1 16:10:39 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

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&#160;<= nums&#160;<= 109
nums&#160;是一个非递减数组
-109&#160;<= target&#160;<= 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;
        }
};
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-6-15 19:17

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表