区间查找

给定一个排序数组nums(nums中有重复元素)与目标值target,如果 target在nums里出现,则返回target所在区间的左右端点下标,[左端点, 右端 点],如果target在nums里未出现,则返回[-1, -1]。 LeetCode 34. Search for a Range

思考

1.可否直接通过二分查找,很容易同时求出目标target所在区 间的左右端点? 2.若无法同时求出区间左右端点,将对目标target的二分查找 增加怎样的限制条件,就可分别求出目标target所在区间 的左端点与右端点?

算法设计

查找区间左端点时,增加如下限制条件: 当target == nums[mid]时,若此时mid == 0或nums[mid-1] < target,则说明mid即 为区间左端点,返回;否则设置区间右端点为mid-1。

查找区间右端点时,增加如下限制条件: 当target == nums[mid]时,若此时mid == nums.size() – 1或 nums[mid + 1] > target ,则说明mid即为区间右端点;否则设置区间左端点为mid + 1

流程:

int left_bound(std::vector<int> &nums, int target){
    int begin = 0;
    int end = noms.size() -1 ;
    while(begin <= end){
        int mid = (begin + end) / 2;
        if(target == nums[mid]){
            if(mid == 0 || target > nums[mid-1]){
                return mid;
            }
            begin = mid + 1;
        }
        else if(target < nums[mid]){
            end = mid -1;
        }
        else if(target > nums[mid]){
            begin = mid +1;
        }
    }
    return -1;
}
区间右端点
int right_bound(std::vector<int> &nums,int target){
    int begin = 0;
    int end = nums.size() -1;
    while(begin <= end){
        int mid =( begin + end )/2;
        if(target == mid){
            if(mid = nums.size()-1 || nums[mid+1] > target){
                return mid;
            }
            begin = mid +1;
          }
        else if(target < nums[mid]){
            end = mid -1;
        }
        else if(target > nums[mid]){
            begin = mid+1;
        }
     }
return -1;
}
leetcode测试
class Solution{
public:
    std::vector<int> searchRange(std::vector<int>&nums, int target){
        std::vector<int> result;
        result.push_back(left_bound(nums,target));
        result.push_back(right_bound(nums,target));
        return result;
    }
};

int main(){
    int test[] = {5,7,7,8,8,8,8,10};
    std::vector<int> nums;
    Solution solve;
    for(int i = 0;i< 8;i++){
        nums.push_back(test[i]);
    }
    for(int i= 0;i< 12;i++){
        std::vector<int> result = solve.searchRange(nums,i);
        printf("%d : [%d,%d]\n",i, result[0],result[i]);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏五分钟学算法

每天一算:Odd Even Linked List

我们会在每天早上8点30分准时推送一条LeetCode上的算法题目,并给出该题目的动画解析以及参考答案,每篇文章阅读时长为五分钟左右。

12630
来自专栏算法修养

树形DP总结,持续更新

自己做了动态规划的题目已经有了一个月,但是成效甚微,所以来总结一下动态规划,希望自己能够温故知新。这个博客是关于树形dp的,动态规划的一类题目。 ...

81960
来自专栏糊一笑

关于一道面试题【字符串 '1 + (5 - 2) * 3',怎么算出结果为10,'eval'除外】

最近徘徊在找工作和继续留任的纠结之中,在朋友的怂恿下去参加了一次面试,最后一道题目是: 写一个函数,输入一个字符串的运算式,返回计算之后的结果。例如这样的: ...

600100
来自专栏java一日一条

经典数据结构和算法回顾

最近想回过头来看看以前写的一些代码,可叹为何刚进大学的时候不知道要养成写博客的好习惯。现在好多东西都没有做记录,后面也没再遇到相同的问题,忘的都差不多了。只能勉...

10510
来自专栏拭心的安卓进阶之路

Java 集合深入理解(16):HashMap 主要特点和关键方法源码解读

前面我们介绍了 哈希相关概念:哈希 哈希函数 冲突解决 哈希表,这篇文章我们来根据 JDK 1.8 源码,深入了解下使用频率很高的 HashMap 。 读完本...

30450
来自专栏大数据风控

Python中字段抽取、字段拆分、记录抽取

1、字段抽取 字段抽取是根据已知列数据的开始和结束位置,抽取出新的列 字段截取函数:slice(start,stop) 注意:和数据结构的访问方式一样,开始位置...

38780
来自专栏数据结构与算法

BZOJ4653: [Noi2016]区间(线段树 双指针)

按照dls的说法,一般这一类的题有两种思路,一种是枚举一个点$M$,然后check它能否成为答案。但是对于此题来说好像不好搞

11620
来自专栏算法channel

1800字普林斯顿大学课程浓缩笔记:程序员必知的算法之查找和排序算法

老生常谈,偶尔遇到阐述这两类问题相关的极好素材,它们结合示意图,言简意赅,清晰明了。故分享出来。

8700
来自专栏编程

Python内置函数int高级用法

int()函数常用来把其他类型转换为整数,例如: >>>int(3.2) 3 >>>int(1/3) 其实,int是Python内置类型之一,之所以能够当作函数...

29890
来自专栏iOSDevLog

数据结构和算法

数据结构和算法是计算机科学中最重要的概念之一。如果您不熟悉计算机科学或编程,本文将为您提供有关数据结构和算法的概述。这也是Landscape系列的第二集。

19140

扫码关注云+社区

领取腾讯云代金券