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

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

问题描述：

给定一个排序数组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 
#include 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]

更多相关：

  • 二分法：search insert position 插入位置

    问题描述： 给定一个排序数组nums(无重复元素)与目标值target，如果target在nums里 出现，则返回target所在下标，如果target在nums里未出现，则返回target应该 插入位置的数组下标，使得将target插入数组nums后，数组仍有序。 例如： 数组 arr = [2,3,4,6] target = 1...

  • 75. Find Peak Element 【medium】

    75. Find Peak Element 【medium】 There is an integer array which has the following features: The numbers in adjacent positions are different.A[0] < A[1] && A[A.length...

  • 367. Valid Perfect Square

    题目： Given a positive integer num, write a function which returns True if num is a perfect square else False. Note: Do not use any built-in library function such as sqrt...

  • 数据结构（1）有序表查找

     有序表查找 /* 主函数 */public class OrderTableSearch {public static void main(String[] args) {int [] a= {0,1,16,24,35,47,59,62,73,88,99}; System.out.println(FibonacciSearc...

  • 剑指offer：面试题04. 二维数组中的查找

    题目：二维数组中的查找 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 示例: 现有矩阵 matrix 如下： [[1, 4, 7, 11, 15],[2, 5, 8, 12, 1...

  • valgrind 使用 kcachegrind 查看函数运行时间

    安装 首先安装运行分析函数时间的工具 kcachegrind 下载安装包 http://kcachegrind.sourceforge.net/，下载最新的 tar.gz 文件 解压文件，进入解压之后的目录，从 README 中可以找到安装方式，这里记录一下 cmake . make -j8 sudo make install...

  • Linux ISCSI配置

    一、简介 iSCSI（internet SCSI）技术由IBM公司研究开发，是一个供硬件设备使用的、可以在IP协议的上层运行的SCSI指令集，这种指令集合可以实现在IP网络上运行SCSI协议，使其能够在诸如高速千兆以太网上进行路由选择。iSCSI技术是一种新储存技术，该技术是将现有SCSI接口与以太网络(Ethernet)技术结合，使...

  • 记录CSS3 target伪类简介

    CSS3 target伪类是众多实用的CSS3特性中的一个。它用来匹配文档(页面)的URI中某个标志符的目标元素。具体来说，URI中的标志符通常会包含一个”#”字符，然后后面带有一个标志符名称，比如#respond，target就是用来匹配ID为respond的元素的。 现在在页面中，点击一个ID链接后，页面只会跳转到相应的位置，但...

  • flash玩转cookie

    经常有遇到说浏览器与flash之间不好debug,数据不好交流，确实每次遇到都得多写些代码。麻烦！ 这回我打算写个flash类，专门用来解决这些问题。这几天，我就先从cookie的读写开始，写了个cookie类，有了这个类，以后我就能直接在flash里面操作cookie了。一劳永逸，大伙如果觉得有用就拿去吧。我已经放在了google...

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

©2024 11GX.COM