当前位置：首页 > 编程日记 > 正文

二分法：查找区间search for a range

编程日记 2024-04-19 03:30:00

问题描述：
给定一个排序数组nums(nums中有重复元素)与目标值target，如果 target在nums里出现，则返回target所在区间的左右端点下标，[左端点, 右端点]，如果target在nums里未出现，则返回[-1, -1]。

例如:
arr = [2,3,4,4,4],target = 4,最终结果为[2,4]
arr = [2,3,4,5,6],target = 4,最终结果为[2,2]

分析：
最终的结果为一个区间，区间的话肯定有左端点，右端点。

题目是给定了一个有序数组，那么我们的目标就是确认左端点和右端点分别是多少即可。左端点即左侧再有没有比左端点更小的数值了，右端点即右侧再也没有比右端点更大小数值了。

确认左端点的过程如下:
arr = [2,3,4,4,4],target = 4,那么需要走一遍二分查找的整个过程
如果我们发现arr[mid] == target,这个时候仍然需要进行判断，即mid == 0 或者arr[mid-1] < target，那么才能够认为此时 left = mid；即此时arr[mid]的左侧已经没有和target相等的节点了。

确认右端点的过程如下:
arr = [2,3,4,4,5],target = 4,那么同样需要走一遍二分查找的整个过程
如果我们发现arr[mid] == target,这个时候仍然需要进行判断，即mid == arr.size()-1 或者arr[mid+1] > target，那么才能够认为此时 right = mid；即此时arr[mid]的右侧已经没有和target相等的节点了。

以上过程实现如下:

pair<int,int> get_target_range(std::vector<int> &arr, int target) {int begin = 0;int end = arr.size() - 1;pair<int,int> range;range.first = -1;range.second = -1;/*计算左边界*/while(begin <= end) {int mid = (begin + end) / 2;if (arr[mid] == target) {if (mid == 0 || arr[mid - 1] < target) {//arr[mid]左侧没有比target更小的range.first = mid;break;} end = mid - 1; //控制左侧的遍历} else if (arr[mid] > target) {end = mid - 1;} else {begin = mid + 1;}}/*计算右边界*/begin = 0;end = arr.size() - 1;while(begin <= end) {int mid = (begin + end) / 2;if (arr[mid] == target) {/*arr[mid]右侧没有比target更大的*/if (mid == arr.size() - 1 || arr[mid + 1] > target) {range.second = mid;break;} begin = mid + 1;} else if (arr[mid] > target) {end = mid - 1;} else {begin = mid + 1;}}return range;
}

测试代码如下:

#include <iostream>
#include <vector>using namespace std;
pair<int,int> get_target_range(std::vector<int> &arr, int target) {int begin = 0;int end = arr.size() - 1;pair<int,int> range;range.first = -1;range.second = -1;while(begin <= end) {int mid = (begin + end) / 2;if (arr[mid] == target) {if (mid == 0 || arr[mid - 1] < target) {range.first = mid;break;} end = mid - 1;} else if (arr[mid] > target) {end = mid - 1;} else {begin = mid + 1;}}begin = 0;end = arr.size() - 1;while(begin <= end) {int mid = (begin + end) / 2;if (arr[mid] == target) {if (mid == arr.size() - 1 || arr[mid + 1] > target) {range.second = mid;break;} begin = mid + 1;} else if (arr[mid] > target) {end = mid - 1;} else {begin = mid + 1;}}return range;
}int main() {std::vector<int> arr1;int n;cin >> n;for (int i = 0;i < n; ++i) {int tmp;cin >> tmp;arr1.push_back(tmp);}int target;cin >> target;cout << "[" << get_target_range(arr1, target).first << "," << get_target_range(arr1, target).second << "]"; return 0;
}

输出如下:

#输入
5
2 3 4 4 4
#输入target
4
#输出
[2,4]#输入
5
4 4 4 4 4
#输入target
4
#输出
[0,4]

https://www.dkcj.cn/info/4888.html

二分法：查找区间search for a range

相关文章：

c语言向表格内存入数据,怎么实现横向到存入多个单元格,在列数固定的报表中逐格横向填充数据并折行...

设计模式之简单工厂模式

zendserver的版本是怎么回事？免费版哪里去了？

sql-case when 条件1 then 取值1 when 条件2 then 取值2 else 取值3 end

二叉树：二叉搜索树的创建和插入

ie7和ie8 select使用jquery clone不兼容处理

c语言中floox的头文件,PC-1211袖珍计算机在合成氨厂生产中的应用第五讲循环语句(FOR-NEXT语句)...

C#Winform+WindowsAPI做个剪贴板无缝自动保存器（视频截图利器）

Kafka配置SASL/PLAIN认证

二叉树：二叉搜索树的编码和解码

springmvc3.2+spring+hibernate4全注解方式整合（一）

c 应用程序多语言版本,c – 在win32 API应用程序中实现全球化/多语言功能

整数展示分数和整形数的四则运算

二叉树：二叉搜索树实现逆序数问题

C语言文件实验要求,实验教学的目的和要求.doc

这些工作的日子

python基础类型

linux系统目录树/内核源码目录树

顺时针打印二维数组C语言递归,按顺时针打印矩阵

降低噪声和电磁干扰的原则

翻译：java.util.regex.Pattern

学习笔记53—Wilcoxon检验和Mann-whitney检验的区别

s-systemtap工具使用图谱（持续更新）

2014 Super Training #8 C An Easy Game --DP

qq分享组件 android,移动端，分享插件

MySQL中更改表操作

Maven-环境配置

分布式存储(ceph)技能图谱（持续更新）

android如何查看方法属于哪个类,Android Studio查看类中所有方法和属性

读javascript高级程序设计03-函数表达式、闭包、私有变量