[力扣_34] 在排序数组中查找元素的第一个和最后一个位置

题目入口:点击进入

相关算法:

  • 二分搜索——时间复杂度O(logn),空间复杂度O(1)

思路和算法:

这题考的是利用二分法寻找边界,如何利用二分法左右逼近,这道题有一个误区,虽然看见有序数组都不难想到使用二分查找的方法去写,但是当求得第一个target的时候,容易使用线性搜索左右扩散去求,这样是不符合要求的。

正确的做法是继续使用二分搜索

二分搜索

对于二分搜索相信大家都不陌生了,主要思路是通过比较中间位置的值和target去确定target在哪个区间内,同时缩小搜索空间 [收缩边界] 因为数组是有序的,所以在中间位置mid上,总有以下条件成立:

  • [nums[left],nums[mid-1]] 严格小于 nums[mid]
  • [nums[mid+1],nums[right]] 严格大于 nums[mid]

那么我们如何利用二分搜索分特性去左右逼近边界呢?

如下列这个数组:我们先通过二分查找逼近其左边界

img**nums[mid] > target
代表target在[left,mid)这个区间内
则收缩右边界
right = mid -1**

img**nums[mid] == target
代表target的左边界一定不在 (mid,right] 这个区间内
则收缩右边界,同时记录mid的下标[1,x]
right == mid -1**

img**nums[mid] < target
代表target的左边界一定不在[left,mid) 这个区间内
则收缩左边界
left = mid +1**

此时 left 大于 right 则 结束循环。

这个时候我们已经找到其左边界,就是 [1,x] ,整理下以上的状态变化:

  • 循环条件(left <= right)
  • 如果 nums[mid] >= target 时

    • right = mid -1
  • 否则

    • left = mid +1

通过上述我们能写出代码如下所示:

void Findleft(int *nums,int left,int right,int target,int *LEFT)
{
    int mid;
    while(left <= right)
    {
       mid=(left+right)/2;
       if(nums[mid]==target) *LEFT=mid;
       if(nums[mid] >= target)//大于或等于,表示右边不可能出现目标元素
           right=mid - 1;
       else//小于,表示左边不可能出现目标元素
           left=mid + 1;
    }
    if(nums[left]==target) return left;
    return -1;
}

我们可以通过同样的方法求得右边界,而与求左边界不同的是,求右边界需要不断向右移动,去逼近右边,得到符合条件 也就是 最右边不等于 target 的那个下标。

img**nums[mid] > target
代表target在[left,mid)这个区间内
则收缩右边界
right = mid -1**

img**nums[mid] == target
代表target的右边界一定不在 [left,mid) 这个区间内
则收缩左边界,同时记录其mid 的下标: [1,1]
left = mid + 1**

img**nums[mid] == target
代表target的右边界一定不在 [left,mid) 这个区间内
则收缩左边界,同时记录其mid 的下标: [1,2]
left = mid + 1**

img**nums[mid] == target
代表target的右边界一定不在 [left,mid) 这个区间内
则收缩左边界,同时记录其mid 的下标: [1,3]
left = mid + 1**

这个时候 left > right ,则退出循环,同时我们已经找到左右边界的 下标了:[1,3]

我们来整理下上述状态变化:

  • 循环条件(left <= right)
  • 如果 nums[mid] <= target 时

    • left = mid + 1
  • 否则right = mid -1

同样我们能根据上述代码写出求右边界的代码如下所示:

void Findright(int *nums,int left,int right,int target,int *RIGHT)
{
    int mid;
    while(left <= right)
    {
       mid=(left+right)/2;
       if(nums[mid]==target) *RIGHT=mid;
       if(nums[mid] <= target)//小于它,则代表左边一定没有它需要的值
           left=mid + 1;
       else
           right=mid - 1;
    }
    return;
}

我们把状态转移想明白后,考虑下临界值和特殊情况,题目中给出,如若数组中没有该数字,则返回-1 -1 ,我们只需要将下个记录变量全部初始化为 -1 然后判断在第一次寻找左边界的时候是否等于 -1 ( 记录值是否改变) 即可确定数组中是否存在target。完整代码如下所示:

void Findleft(int *nums,int left,int right,int target,int *LEFT)
{
    int mid;
    while(left <= right)
    {
       mid=(left+right)/2;
       if(nums[mid]==target) *LEFT=mid;
       if(nums[mid] >= target)//大于或等于,表示右边不可能出现目标元素
           right=mid - 1;
       else//小于,表示左边不可能出现目标元素
           left=mid + 1;
    }
    if(nums[left]==target) return left;
    return -1;
}
void Findright(int *nums,int left,int right,int target,int *RIGHT)
{
    int mid;
    while(left <= right)
    {
       mid=(left+right)/2;
       if(nums[mid]==target) *RIGHT=mid;
       if(nums[mid] <= target)//小于它,则代表左边一定没有它需要的值
           left=mid + 1;
       else
           right=mid - 1;
    }
    return;
}

int* searchRange(int* nums, int numsSize, int target, int* returnSize){

    *returnSize=2;
    int *res=(int*)malloc(sizeof(int)*2);
    
    if(numsSize==0||!res){
        res[0]=-1;
        res[1]=-1;
        return res;
    }
    
    int left=0;
    int right=numsSize-1;

    int LEFT= -2;
    int RIGHT= -2;

    Findleft(nums,left,right,target,&LEFT);
    if(LEFT==-2) {
        res[0]=-1;
        res[1]=-1;
        return res;
    }
   // printf("%d\n",FirstIndex);
    Findright(nums,left,right,target,&RIGHT);
    
    res[0]=LEFT;
    res[1]=RIGHT;
    return res;
}

然后......暴力解法超 百分百 二分查找超 60......

本文链接:

https://nullcode.fun/81.html
1 + 7 =
快来做第一个评论的人吧~