二分查找确定lower_bound和upper_bound
2024-08-30 07:04:28
lower_bound当target存在时， 返回它出现的第一个位置，如果不存在，则返回这样一个下标i：在此处插入target后，序列仍然有序。
代码如下：
int lower_bound(int* nums, int numsSize, int target) {
//注意left和right的初始值必须是left = 0, right = numsSzie, 因为插入的位置可能是[0,numsSize]
int left = 0;
int right = numsSize;
int mid;
while (left < right)
{
mid = left + (right - left) / 2;
if (nums[mid] >= target)
right = mid;
else
left = mid + 1;
}
return left;
}
尽管查找区间是[0, numsSize)，但返回值区间却是[0, numsSize]。因此right的初始值必须为numsSize，而不是numsSize - 1。
当nums[mid] == target时，至少已经找到了一个，而左边可能还有，因此区间变为[left, mid];
当nums[mid] > target时，所求位置不可能在后面，但有可能是mid，因此区间变为[left, mid]；
当nums[mid] < target时，mid和前面都不可行，因此所求区间为[mid+1, right]。
合并一下，当nums[mid] >= target时，所求区间为[left, mid]；当nums[mid] < target时，所求区间为[mid + 1, right]。
类似地，可以写一个upper_bound程序，当target存在时， 返回它出现的最后一个位置的后面一个位置，如果不存在，则返回这样一个下标i：在此处插入target后，序列仍然有序。
int upper_bound(int* nums, int numsSize, int target) {
//注意left和right的初始值必须是left = 0, right = numsSzie, 因为插入的位置可能是[0,numsSize]
int left = 0;
int right = numsSize;
int mid;
while (left < right)
{
mid = left + (right - left) / 2;
if (nums[mid] <= target)
left = mid + 1;
else
right = mid;
}
return left;
}
最新文章
- 深入理解计算机系统（4.1）---X86的孪生兄弟，Y86指令体系结构
- 记一次SQLServer数据库误删数据找回
- Sublime Text 前端插件推荐
- bzoj3047: Freda的传呼机 && 2125: 最短路
- 《Java程序员面试笔试宝典》之字符串创建与存储的机制是什么
- GIT的下载、安装、与使用
- ARC引用计数
- spring mvc中，直接注入的HttpServletRequst是否安全呢?
- 201521123112《Java程序设计》第13周学习总结
- HDU [P2819] swap
- C++关于Union使用的部分总结
- Django rest framework（6）----序列化（2）
- ios dispatch_async使用
- TCP/IP协议 模型
- 解决 ionic 中的 CORS（跨域）
- Visual Studio 2017 版本 15.5.5
- Inferred type 'S' for type parameter 'S' is not within its bound;
- python中集合及运算
- Barricade HDU - 5889（最短路+最小割）
- Jenkins-在节点上执行copy命令，将节点机上的文件拷贝到映射的网络驱动盘中报错，访问被拒绝 找不到指定驱动器