[力扣_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......