2025寒假备战蓝桥杯02---朴素二分查找升级版本的学习+分别求解左右端点

1.朴素二分查找的升级版

和之前介绍的这个二分查找相比，我觉得这个区别就是我们的这个二分查找需要找到的是一个区间，而不是这个区间里面的某一个元素的位置；

image-20250120234321180

2.查找左端点

1）首先就是我们的这个循环的条件：left<right; 2）其次就是我们的判断的这个语句： x<t，这个t就是我们的target目标值；这个时候和我们的朴素二分一样，就是让这个left=mid+1; 但是当这个x>=t的时候，我们不再是让这个right=mid-1了，而是让这个right=mid，因为这个时候是判断的区间，所以这个mid可能就是我们想要的这个数值；； 3）之前我们确定这个mid的时候是这个+1或者是不+1都是可以的，因为当是偶数的时候，两个情况下对应的这个数值都失败可以帮助我们判断的； 但是在这个里面，我们的终点求解的时候，就应该是这个不加1的版本才可以；

image-20250120235325363

3.查找右端点

1）这个和上面的恰好是反过来的，无论是这个终点的求解，还是这个判断和位置的变换，都是和上面的放过来； 上面的取等号的，我们下面的查找右端点就不用取等号，反之，如果上面没取，我们这个就需要进行相等情况下的判断； 2）其次就是这个里面的终点元素的判断： left+(right-left+1)/2和上面的也是不同的，上面的是不要+1的；

image-20250120235341957

4.代码的编写

1）首先定义一个数组，里面的两个元素都是-1，这个处理的就是我们的这个示例里面的第三种情况； 2）下面就是分别去查找我们的左端点和右端点，按照上面介绍的这个思路即可； 3）左端点： left<right作为循环的条件； mid求解的时候不需要+1的操作； x<target对应的就是我们的left=mid+1; x>=target对应的就是我们的mid=right; return的时候其实这个left和right指向的就是一个位置，因此当我们往数组里面搁置的时候，left和right都是可以的；

image-20250120235648864

4）下面的这个是右端点的判断的逻辑代码： left<right作为我们的判断的条件； mid求解的时候需要加上1； x<=target对应的这个left=mid； x>target的时候,right=mid减去一； 这个找到端点之后，直接把这个下标放到我们的ret数组里面的第二个元素的位置即可；

image-20250120235816734