34. 在排序数组中查找元素的第一个和最后一个位置

题目:34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

此题同35，很明显上了一个台阶

思路分析:就是左右边界分辨判断一下，而后得出左右边界后有三种情况

• 情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
• 情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
• 情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}

对应代码:

    if(leftboard == -2 || rightboard == -2)
    return{-1,-1};//情况一，在边界外的不会赋值
    else if(rightboard - leftboard> 1)
    return{leftboard + 1,rightboard - 1}; 要把左边界加回去，右边界减回去
    else
    return{-1,-1};//满足在数组范围中间的，差值不会大于1

我看了近半个小时，错的点在这。。。找左边界时，可以相等，得到不包含其的左边界值，同右边界思想一致

  if(nums[mid] >= target)
        { 
        right = mid - 1 ;// 寻找左边界，就要在nums[middle] == target的时候更新right
        getleft = right ;

完整代码:

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
    int leftboard = getleft(nums , target);
    int rightboard = getright(nums , target);
    if(leftboard == -2 || rightboard == -2)
    return{-1,-1};
    else if(rightboard - leftboard> 1)
    return{leftboard + 1,rightboard - 1}; 
    else
    return{-1,-1};
    }
private:
    int getright(vector<int>& nums, int target)//找右边界
     {
       int left = 0 ;int right = nums.size()-1;
       int getright = -2;
       while(left <= right)
       {
        int mid = (left + right)/2;
        if(nums[mid] > target)
        right = mid - 1 ;
        else
        {
        left = mid + 1 ;
        getright = left; // 当nums[middle] == target的时候，更新left，这样才能得到target的右边界
        }
       }
       return getright;
     }

     int getleft(vector<int>& nums, int target)//找左边界
     {
       int left = 0 ;int right = nums.size()-1;
       int getleft = -2;
       while(left <= right)
       {
        int mid = (left + right)/2;
        if(nums[mid] >= target)
        { 
        right = mid - 1 ;// 寻找左边界，就要在nums[middle] == target的时候更新right
        getleft = right ;
        }
        else
        left = mid + 1 ;
       }
       return getleft;
     }
    
};

原文地址：https://blog.csdn.net/zengxuan151168/article/details/142745798

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！