[力扣_34] 在排序数组中查找元素的第一个和最后一个位置
题目入口:点击进入
相关算法:
- 二分搜索——时间复杂度O(logn),空间复杂度O(1)
思路和算法:
这题考的是利用二分法寻找边界,如何利用二分法左右逼近,这道题有一个误区,虽然看见有序数组都不难想到使用二分查找的方法去写,但是当求得第一个target的时候,容易使用线性搜索左右扩散去求,这样是不符合要求的。
正确的做法是继续使用二分搜索
二分搜索
对于二分搜索相信大家都不陌生了,主要思路是通过比较中间位置的值和target去确定target在哪个区间内,同时缩小搜索空间 [收缩边界] 因为数组是有序的,所以在中间位置mid上,总有以下条件成立:
- [nums[left],nums[mid-1]] 严格小于 nums[mid]
- [nums[mid+1],nums[right]] 严格大于 nums[mid]
那么我们如何利用二分搜索分特性去左右逼近边界呢?
如下列这个数组:我们先通过二分查找逼近其左边界
nums[mid] > target
代表target在[left,mid)这个区间内
则收缩右边界
right = mid -1
nums[mid] == target
代表target的左边界一定不在 (mid,right] 这个区间内
则收缩右边界,同时记录mid的下标[1,x]
right == mid -1
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 的那个下标。
nums[mid] > target
代表target在[left,mid)这个区间内
则收缩右边界
right = mid -1
nums[mid] == target
代表target的右边界一定不在 [left,mid) 这个区间内
则收缩左边界,同时记录其mid 的下标: [1,1]
left = mid + 1
nums[mid] == target
代表target的右边界一定不在 [left,mid) 这个区间内
则收缩左边界,同时记录其mid 的下标: [1,2]
left = mid + 1
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......